代码

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=3;
int ch[N][2];
int val[N];
int sum[N];
int rev[N];
int fa[N];
int Isnot_Root(int x){
	return ch[fa[x]][0]==x||ch[fa[x]][1]==x;
}
int Is_Son(int fat,int x){
	return ch[fat][1]==x;
}
void PushUp(int x){
	sum[x]=val[x];
	if(ch[x][0])sum[x]+=sum[ch[x][0]];
	if(ch[x][1])sum[x]+=sum[ch[x][1]];
}
void Push_Rev(int x){
	swap(ch[x][0],ch[x][1]);
	rev[x]^=1;
}
void PushDown(int x){
	if(rev[x]){
		if(ch[x][0])Push_Rev(ch[x][0]);
		if(ch[x][1])Push_Rev(ch[x][1]);
		rev[x]=0;
	}
}
void Rotate(int x){
	int y=fa[x];
	int z=fa[y];
	int son=Is_Son(y,x);
	if(Isnot_Root(y)){
		ch[z][Is_Son(z,y)]=x;
	}
	fa[x]=z;
	ch[y][son]=ch[x][son^1];
	fa[ch[x][son^1]]=y;
	ch[x][son^1]=y;
	fa[y]=x;
	PushUp(y);
}
int S[N];
void Splay(int x){
	int u=x,top=0;
	S[++top]=u;
	while(Isnot_Root(u))u=fa[u],S[++top]=u;
	while(top)PushDown(S[top--]);
	while(Isnot_Root(x)){
		int y=fa[x];
		int z=fa[y];
		if(Isnot_Root(y)){
			(Is_Son(z,y)^Is_Son(y,x))?Rotate(x):Rotate(y);	
		}
		Rotate(x);
	}
	PushUp(x);
}
void Access(int x){
	for(int y=0;x;y=x,x=fa[x]){
		Splay(x);
		ch[x][1]=y;
		PushUp(x);
	}
}
void Make_Root(int x){
	Access(x);
	Splay(x);
	Push_Rev(x);
}
void Link(int x,int y){
	Make_Root(x);
	fa[x]=y;
}
void Cut(int x,int y){
	 Make_Root(x);
	 Access(y);
	 Splay(y);
	 fa[x]=0;
	 ch[y][0]=0;
}
int plus(int x,int y){
	memset(ch,0,sizeof(ch));
       memset(fa,0,sizeof(fa));
      memset(sum,0,sizof(sum));
    memset(rev,0,sizeof(rev));
val[1]=x;
	val[2]=y;
	Link(1,2);
	
	Make_Root(1);
	Access(2);
	Splay(2);
	//cout<<fa[1]<<" "<<sum[2]<<'\n';
	//PushUp(2);
	cout<<sum[2]<<'\n';
	return 0;
}

评测结果