动态树（ Dynamic Trees ）问题, 即要求我们维护一个由若干棵子结点无序的有根树组成的森林。 要求这个数据结构支持对树的分割，合并，对某个点到它的根的路径的某些操作, 以及对某个点的子树进行的某些操作。（来源——QTREE解法的一些研究byYangZhe）
解决动态树问题有很多种方法 ，这里介绍 Link - Cut Trees ，它不能够实现“对某个点的子树进行的某些操作”，但是对于大部分动态树问题来说还是够用了（其他动态树好像比较冷门）。
动态树的主体思想和树链剖分很相似（树链剖分戳这里），非常频繁地运用到了 Splay Tree （Splay模板戳这里）
无关内容： 还有一种动态树叫做Euler-Tour Trees，能够实现对子树的某些操作，然而我并没有找到有任何关于它的中文文献。。。 所以等到我哪天英文达到了那个水平再去学吧。。。。
Link - Cut Trees 是由 Sleator 和 Tarjan 发明的，这里膜拜一下 Tarjan （Orz），LCT,LCA,LCP的发明者中都有他的名字。。。（还有很多很多算法。。。）
定义一些神奇的称呼：
access(x) ：访问节点 x PreferredChild：如果结点 v 的子树中, 最后被访问的结点在子树w中, 这里 w 是v的儿子, 那么就称 w 是v的 PreferredChild PreferredEdge ：每个点到它的 PreferredChild 的边称作 PreferredEdge PreferredPath ：由 PreferredEdge 连接成的不可再延伸的路径称为 PreferredPath其中 access(x) 是 Link - Cut Trees 最基本的操作，没有之一。就像 Splay 操作对于 Splay Tree 一样。
容易得出整棵树就被划分成了若干条 PreferredPath 。对每条 PreferredPath ， 用这条路上的点的深度作为关键字, 用一棵平衡树来维护它（一般使用Splay，理论上Treap也可以，可是我从没有看见有人这样做过）。然后这棵平衡树就被叫做 AuxiliaryTree 。我们把 AuciliaryTree 中深度最小的节点的父亲节点称为 PathParent 。
Link - Cut Trees 就是将要维护的森林中的每棵树 T 表示为若干个 AuxiliaryTree ， 并通过 PathParent 将这些 AuxiliaryTree 连接起来的数据结构
一旦我们调用 access(x) ，那么从点 x 到根结点的路径就成为一条新的 PreferredPath。 如果路径上的某个节点 u 不是它的父亲v的 PreferredChild ， 那么我们要将 v 的PreferredChild变为 u ， 原本包含v的 PreferredPath/AuxiliaryTree 将不再包含节点 v 及其之上的部分。
具体操作： 首先，我们将节点v到它的 PreferredChild 的边删除，将节点 v Splay到它所属的 AuxiliaryTree 的根，然后将 v 与它的右子树断开，使它的右子树变为一棵新的AuxiliaryTree，并将它的 PathParent 设置为节点 v 。 然后，如果点v所属的 PreferredPath 并不包含根结点，设它的 PathParent 为 u ， 那么需要将u旋转到 u 所属的AuxiliaryTree的根，并用点 v 所属的AuxiliaryTree替换到点 u 所属的AuxiliaryTree中点 u 的右子树， 再将原来点u所属的 AuxiliaryTree 中点 u 的右子树的PathParent设置为 u 。
重复以上操作，直到到达包含根结点的PreferredPath。 给出几张图片，方便大家更好地理解 access(x) 操作。
有了 access(x)操作 剩下的操作都变得十分地简单。
找到节点 x 所在树的根节点。
具体操作： 先access(x)，然后将 x Splay到所在 AuxiliaryTree 的根节点。找到这棵 AuxiliaryTree 最左端的点即可。
断开 x 与其父亲节点的边。
具体操作： 先access(x)，然后将 x Splay到所在 AuxiliaryTree 的根节点。断开 x 和父亲节点的边。
让 v 成为w的新的儿子。其中 v 是一棵树的根结点，并且v和 w 是不同的两棵树中的结点。
具体操作： 先访问v，然后修改 v 所属的AuxiliaryTree的 PathParent 为 w ，然后再次访问v。
我们发现，当一个节点u位于所在的 AuxiliaryTree 的根节点时，它的父亲为0，我们可以做相应的优化，不再需要 PathParent 数组，根节点的父亲设置为 PathParent ，然后增加一个 bool 型数组，表示一个节点是否为根节点，这样可以节省一部分空间。
struct LCT { bool root[MAXN]; int fa[MAXN], ch[MAXN][2]; void init() { memset(fa, 0, sizeof(fa)); memset(ch, 0, sizeof(ch)); memset(root, true, sizeof(root)); } void Rotate(int p, bool t) { int f = fa[p]; fa[ch[f][t^1] = ch[p][t]] = f; if(!root[f]) ch[fa[f]][ch[fa[f]][1]==f] = p; else root[p] = !(root[f] = false); fa[p] = fa[f]; ch[fa[f] = p][t] = f; } void splay(int x) { while(!root[x]) { int p = fa[x]; if(root[p]) { Rotate(x, x==ch[p][0]); break; } bool f = x==ch[p][0], f1 = p==ch[fa[p]][0], f2 = p==ch[fa[p]][1]; Rotate(f?f1?p:x:f2?p:x, f); Rotate(x, f1); } } void access(int u) { int v = 0; while(u) { splay(u); root[ch[u][1]] = !(root[v] = false); ch[u][1] = v; u = fa[v = u]; } } int find_root(int v) { access(v); splay(v); while(ch[v][0]) v = ch[v][0]; splay(v); return v; } void cut(int v) { access(v); splay(v); root[ch[v][0]] = true; ch[v][0] = fa[ch[v][0]] = 0; } void join(int v, int w) { access(v); fa[v] = w; access(v); } };以下是裸题： HNOI2010 bounce 弹飞绵羊 题目戳这里 题解戳这里 SDOI2008 cave 洞穴勘测 题目戳这里 HDU4010 Query on The Trees 题目戳这里 SPOJ00913 Query on a tree II 题目戳这里
