经过一个下午的折腾，经过四个小时的debug，我的LCT基本定型了。。。
为了加深理解大概写点。。。
本文地址：http://blog.csdn.net/u012457935/article/details/19015059
其实动态树是一类问题啊，这个问题包含了很多的分治，具体可以去fhq666看，不过我们大多树情况还是把LCT(link cut tree)称为动态树
好吧不废话了。。。
动态树：
是一种基于树上操作的数据结构，程序大概只有几k但是却可以实现许多操作。（写前最好有树链剖分的基础）
实际上这种数据结构与树链剖分有异曲同工之处，都是化树为链，只不过树链剖分是在线段树上实现的，而动态树是在splay上的实现的。
当然，可以理解为动态树是熟料剖分的拓展，从功能上可以看出来。。
还有一个重点就是动态树所维护的树是可以动的（废话。。。。）这就导致树链剖分中的轻重边定义失效了，所以动态树上的轻重边的定义是基于操作的，不过这并不重要，原来在树链剖分中的各种定理也是可以用的。。要是不能用...........你就别用了。
这大概就是动态树的基础知识。。。个人认为已经比较详细了。。
动态树的基本操作：
首先是最基础的access操作：
即将当前节点到root上的所有边都变为重边
其他是一些基本的操作：
build_tree
很简单啊就是每个点一棵树（请自行区分本文中的树是指splay还是题中的树）
evert
将当前节点x到当前根节点的所有树边都反向，经过这样的一次操作以后根就是当前节点了。。
cut
将节点x与其树中的边删去
link
使得节点y成为x的孩子
find
找到当前节点x在树中的根节点。
下面将一些具体实现的东西：
①access(x)
首先如果当前节点x与root在一棵树中，那么直接解决问题了就
否则设u为x所在树的path_parent，那么将u通过splay操作转到根，然后用x所在的树代替u的右子树。同时将原来u的右子树w的path_parent设为x
②find(x)
首先对当前节点access（我说是基础吧。。。）然后你懂得
③evert(x)
这个操作的正经定义应该是是节点x成为当前树的根
不过这等价于x到root的边都取反
首先还是access，然后在平衡树上取反嘛。。。。正常操作是o(n)的。。。。
不过我们可以借鉴线段树上的标记操作，同样给节点打上res操作，这样就可以了！不过一定要及时正确的使用down函数进行标记的下放，要不然多放了会tle，少放了会wa
④link(x,y)
为了保证合并后的树是合法的，我们首先要使x成为其所在树的根节点，同时将x splay到根，此时x的左子树是空的（废话。。。。）我们此时就可以把y也splay到他所在树的根然后连到x的左子树上。
好机智！
⑤cut(x,y)
首先将x置为根，在对y进行access，那么这个时候xy就在一棵平衡树中了，这个时候我们只需要分离x和他的左子树目的就达成了。。。
这些就是基本的操作了。。如果有什么更神的操作再说。。。
---------------------------------------------------------by-----------------wbysr-------------------------------------------------------------------------------------------------------------------------------------------------
下面是例题bzoj2049的代码，这是个模板题，建议自己写写。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<algorithm>
#define MAX 10010
using namespace std;
int n,m;
struct anode
{
int id,father,path_parent,res;
int child[2];
};
struct LinkCutTree
{
anode node[MAX];
int cnt,location[MAX];
void build(int x)
{
int p=++cnt;
location[x]=p;
node[p].father=node[p].child[0]=node[p].child[1]=node[p].res=0;
node[p].id=x;
}
void down(int x)
{
if(!node[x].res)
return;
node[x].res=0;
node[node[x].child[0]].res^=1;
node[node[x].child[1]].res^=1;
swap(node[x].child[0],node[x].child[1]);
}
void rotate(int p)
{
int q=node[p].father,y=node[q].father,x=(node[q].child[1]==p);
down(q);
down(p);
node[node[q].child[x]=node[p].child[x^1]].father=q;
node[node[p].child[x^1]=q].father=p;
node[p].father=y;
node[p].path_parent=node[q].path_parent;
node[q].path_parent=0;
if(y)
node[y].child[node[y].child[1]==q]=p;
return;
}
void splay(int x,int aim=0)
{
while(node[x].father)
{
int fa=node[x].father;
down(fa);
if(node[fa].child[0])
down(node[fa].child[0]);
if(node[fa].child[1])
down(node[fa].child[1]);
rotate(x);
}
}
void access(int x)
{
splay(x);
down(x);
int y=node[x].child[1];
node[x].child[1]=node[y].father=0;
node[y].path_parent=x;
for(y=node[x].path_parent;y;y=node[x].path_parent)
{
splay(y);
down(y);
int r=node[y].child[1];
node[r].father=0;
node[r].path_parent=y;
node[y].child[1]=x;
node[x].father=y;
node[x].path_parent=0;
x=y;
}
splay(x);
}
void cut(int x,int y)
{
evert(x);
access(y);
splay(y);
down(y);
node[node[y].child[0]].father=0;
node[y].child[0]=0;
}
int find(int x)
{
access(x);
splay(x);
down(x);
while(node[x].child[0])
x=node[x].child[0];//printf("xxx %d\n",x);
splay(x);
return x;
}
int get_root(int x)
{
return node[find(x)].id;
}
void evert(int x)//使x成为所在树的根节点
{
access(x);
splay(x);
node[x].res^=1;
down(x);
}
void link(int x,int y)//使x成为y的子节点
{
evert(x);
splay(x);
down(x);
access(y);
splay(y);
down(y);
node[x].child[0]=y;
node[y].father=x;
}
void add(int x,int y)
{
link(location[x],location[y]);
}
void destory(int x,int y)
{
cut(location[x],location[y]);
}
}wbysr;
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
wbysr.build(i);
while(m--)
{
char ss[300];
int u,v;
scanf("%s",ss);
scanf("%d%d",&u,&v);
if(ss[0]==‘C‘)
{
wbysr.add(u,v);
}
else
if(ss[0]==‘D‘)
wbysr.destory(u,v);
else
{
int x=wbysr.get_root(u);
int y=wbysr.get_root(v);
if(x==y)
printf("Yes\n");
else
printf("No\n");
}
}
return 0;
}原文：http://blog.csdn.net/u012457935/article/details/19015059