ダイナミックツリー~LCTまとめ

これは私が開いているダイナミックツリーのテーマです。http://acm.hust.edu.cn/vjudge/contest/view.action?cid=25242#overview
まず、ダイナミックツリーとは何ですか？ダイナミックツリーはダイナミックな森林を維持し、ツリーの合併（2本を1本に合併）をサポートし、分離（ある点を父親とポイントを分ける）、動的LCA、ツリー上のポイント権とサイド権の維持、検索（シングルポイントまたはツリー上のルート）、ルートを変えます。
ここではまず楊哲さんの合宿チームの宿題を紹介します。http://wenku.baidu.com/view/75906f160b4e767f5acfcedb この中にはダイナミックツリーの基本操作紹介が全面的であると同時に、関連証明書もあります。
論文を読んだら、HDOJ 4010を例にLCTについて説明します。
この問題には四つの操作があります。
1、xとyが同じ木にいなければxyの隣にあります。
2、xとyが同じ木にいたらx！yはxを木の根に変えてyとyの父を分離します。
3、xとyが同じ木にいるとxからyまでの経路上のすべてのポイントの値＋w
4、xとyが同じツリーにいる場合はyパスにxを出力する最大値
不正出力-1
YZの作業によると、accessはすべてのダイナミックツリーの操作の基礎であり、一回のaccess（u）操作は点uから根の上のすべての点を深さによって1本のsplayで維持し、左は根の深さより小さく、右は根より大きいので、xからyまでの経路を抽出するなら、xを根に変えてaccess（y）に変えることができます。今後はsplayの上でxの右の子樹は空で、ひっくり返した後にxは深さの最小の点で、つまり根で、ここの反転は怠惰な標識を打つことができて、同様に、鎖の上のと、極値も同様な方法で維持することができます。
これですべての操作が先にaccessしてからsplayとマークします。

#include 
#include 
using namespace std;
#define N 300010
#define INF (1<<30)
struct node
{
	node *p,*ch[2];
	int mx,rev,val,add;
}nodes[N],*cur,*null;
int n,m,u,v,w;
node *newnode(int key)
{
	cur->p=cur->ch[0]=cur->ch[1]=null;
	cur->mx=cur->val=key;
	cur->rev=0;
	return cur++;
}
void init()
{
	null=nodes;
	null->p=null->ch[0]=null->ch[1]=null;
	null->mx=null->val=-INF;
	null->add=0;
	null->rev=0;
	cur=nodes+1;
}
struct dynamictree
{
	bool isroot(node *x)//  
	{
		return x==null || x->p->ch[0]!=x && x->p->ch[1]!=x;
	}
	void pushup(node *x)
	{
		x->mx=max(x->val,max(x->ch[0]->mx,x->ch[1]->mx));
	}
	void pushdown(node *x)
	{
		if(x==null) return;
		if(x->rev)
		{
			x->rev=0;
			if(x->ch[0]!=null) x->ch[0]->rev^=1;
			if(x->ch[1]!=null) x->ch[1]->rev^=1;
			swap(x->ch[0],x->ch[1]);
		}
		if(x->add)
		{
			if(x->ch[0]!=null) x->ch[0]->add+=x->add,x->ch[0]->val+=x->add,x->ch[0]->mx+=x->add;
			if(x->ch[1]!=null) x->ch[1]->add+=x->add,x->ch[1]->val+=x->add,x->ch[1]->mx+=x->add;
			x->add=0;
		}
	}
	void rotate(node *x,int f)
	{
		if(isroot(x)) return;
		node *y=x->p;
		y->ch[!f]=x->ch[f];
		x->p=y->p;
		if(x->ch[f]!=null) x->ch[f]->p=y;
		if(y!=null)
		{
			if(y==y->p->ch[1]) y->p->ch[1]=x;
			else if(y==y->p->ch[0]) y->p->ch[0]=x;
		}
		x->ch[f]=y;
		y->p=x;
		pushup(y);
	}
	void splay(node *x)
	{
		static node *sta[N];
		int top=1;
		sta[0]=x;
		for(node *y=x;!isroot(y);y=y->p)
			sta[top++]=y->p;
		while (top) pushdown(sta[--top]);
		while (!isroot(x))
		{
			node *y=x->p;
			if(isroot(y)) rotate(x,x==y->ch[0]);
			else
			{
				int f=y->p->ch[0]==y;
				if(y->ch[f]==x) rotate(x,!f);
				else rotate(y,f);
				rotate(x,f);
			}
		}
		pushup(x);
	}
	node *access(node *u)
	{
		node *v=null;
		while (u!=null)
		{
			splay(u);
			v->p=u;
			u->ch[1]=v;
			pushup(u);
			v=u;
			u=u->p;
		}
		return v;
	}
	node *link(node *u,node *v)//  
	{
		access(u);
		splay(u);
		u->rev=1;
		u->p=v;
	}
	node *cut(node *u)//  
	{
		access(u);
		splay(u);
		u->ch[0]=u->ch[0]->p=null;
		pushup(u);
	}
	void changeroot(node *u)//  
	{
		access(u)->rev^=1;
	}
	node *getroot(node *u)//  
	{
		access(u);
		splay(u);
		while (u->p!=null) u=u->p;
		splay(u);
		return u;
	}
	bool queryuv(node *u,node *v)//         
	{
		while (u->p!=null) u=u->p;
		while (v->p!=null) v=v->p;
		return u==v;
	}
}splay;
int eu[N],ev[N];
int main ()
{
	while (scanf("%d",&n)!=-1)
	{
		init();
		for(int i=1;iadd+=w;
				q->mx+=w;
				q->val+=w;
			}
			else
			{
				scanf("%d%d",&u,&v);
				if(! splay.queryuv(nodes+u,nodes+v))
				{
					printf("-1
");
					continue;
				}
				splay.changeroot(nodes+u);
				splay.access(nodes+v);
				printf("%d
",splay.getroot(nodes+v)->mx);
			}
		}
		printf("
");
	}
	return 0;
}