--少年你有梦想吗？
--少年你听说过安利吗？
安利一个集训队讲解：http://wenku.baidu.com/view/75906f160b4e767f5acfcedb
关于动态树问题，有多种方法。。LCT是其中比较常用的方法；
LCT这种东西根本没用----by ShallWe
----你真的确定吗（charge）
我之前非常确定。
。。。。。。。。。
LCT的话，比较类似树链剖分，有类似轻重链的东东Preferred Path。不过链剖是用线段树维护，而LCT应用伸展树Splay维护。按深度维护。
动态树可以维护一个动态的森林，支持树的合并（两棵合并成一棵），分离（把某个点和它父亲点分开），动态LCA，树上的点权和边权维护、查询（单点或者树上的一条路径），换根。
具体的几个操作：
Access操作：大体上就是访问这个点。
是所有操作的基础，假设调用了过程ACCESS(v),那么从点v到根结点的路径就成为一条新的PreferredPath.如果路径上经过的某个结点u并不是它的父亲parent(u)的Pre-ferredChild,那么由于parent(u)的PreferredChild会变为u,原本包含parent(u)的PreferredPath将不再包含结点parent(u)及其之上的部分.
时间复杂度是均摊的logn证明详见开头的论文。。
Find_Root操作：在ACCESS(v)之后,根结点一定是v所属的AuxiliaryTree的最小结点.我们先把v旋转到它所属的AuxiliaryTree的根.再从v开始,沿着AuxiliaryTree向左走,直到不能再向左,这个点就是我们要找的根结点.由于使用的是SplayTree数据结构保存AuxiliaryTree,我们还需要对根结点进行Splay操作.
Link操作：进行合并
Cut操作:将之分离
（其实最开始想写指针的QAQ，调不出来TAT）感谢Claris的代码帮助
[应用]
１、 最近公共祖先
询问v,w的最近公共祖先，首先执行access(v)，再执行access(w)，当执行access(w)时，记录最近的一个再上次access中被访问的点，这个点就是最近公共祖先。
每次询问需要O(logN)时间。 ２、 集合的合并与分离
可以支持Link和Find操作，还能支持以某种方式分离，而每个集合操作的时间复杂度为O(logN) ３、 最大流
动态树可以用来优化最短路径增广算法，使每次增广的复杂度降为O(mlogN)，并使总复杂度为O(mnlogN)。 ４、 最小生成树
动态树在最小生成树问题中有许多应用。 比如，最小生成树的增量算法、度限制生成树。还有其他许多种变形
模板：（可以压到很短的，抱歉我又刷屏了）
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
#define N 10010
int f[N],son[N][2],val[N],sum[N],tmp[N];bool rev[N];
bool isroot(int x)
{
return !f[x]||son[f[x]][0]!=x&&son[f[x]][1]!=x;
}//判根
void rev1(int x)
{
if(!x) return;
swap(son[x][0],son[x][1]);
rev[x]^=1;
}//翻转
void pb(int x)
{
if(rev[x])
rev1(son[x][0]),rev1(son[x][1]),rev[x]=0;
}//翻转
void up(int x)
{
sum[x]=val[x];
if(son[x][0])sum[x]+=sum[son[x][0]];
if(son[x][1])sum[x]+=sum[son[x][1]];
}//更新值
void rotate(int x)
{
int y=f[x],w=son[y][1]==x;
son[y][w]=son[x][w^1];
if(son[x][w^1]) f[son[x][w^1]]=y;
if(f[y])
{
int z=f[y];
if(son[z][0]==y)son[z][0]=x;
else if(son[z][1]==y)son[z][1]=x;
}
f[x]=f[y];f[y]=x;
son[x][w^1]=y;up(y);
}//旋转
void splay(int x)
{
int s=1,i=x,y;tmp[1]=i;
while(!isroot(i)) tmp[++s]=i=f[i];
while(s) pb(tmp[s--]);
while(!isroot(x))
{
y=f[x];
if(!isroot(y))
{
if((son[f[y]][0]==y)^(son[y][0]==x))
rotate(x); else rotate(y);
}
rotate(x);
}
up(x);
}//伸展
void access(int x)
{
for(int y=0;x;y=x,x=f[x])
splay(x),son[x][1]=y,up(x);
}//访问
int root(int x)
{
access(x);splay(x);
while(son[x][0]) x=son[x][0];
return x;
}//换根
void makeroot(int x)
{
access(x);
splay(x);
rev1(x);
}
void link(int x,int y)
{
makeroot(x);
f[x]=y;
access(x);
}
void cutf(int x)
{
access(x);
splay(x);
f[son[x][0]]=0;
son[x][0]=0;
up(x);
}
void cut(int x,int y)
{
makeroot(x);
cutf(y);
}//分离
int ask(int x,int y)
{
makeroot(x);
access(y);
splay(y);
return sum[y];
}//查询值
int find(int x)
{
access(x);
splay(x);
int y=x;
while(son[y][0]) y=son[y][0];
return y;
}//判断连通性（类LCA）
int main()
{
return 0;
}