首页 > 代码库 > 动态树LCT小结
动态树LCT小结
最开始看动态树不知道找了多少资料，总感觉不能完全理解。但其实理解了就是那么一回事。。。动态树在某种意思上来说跟树链剖分很相似，都是为了解决序列问题，树链剖分由于树的形态是不变的，所以可以通过预处理节点间的关系，将树转化成连续的区间，再加以其它的数据结构，便能以较快的速度处理序列的修改和查询。
而动态树的问题，是包括了树的合并和拆分操作。这个时候，通过预处理实现的静态树的序列算法不能满足我们的要求，于是我们需要一颗‘动态’的树，能在O(logN)的时间复杂度，处理所有操作。
Splay实现的Link/cut tree
Splay能够维护一颗树的信息，我们将多颗Splay树，通过从下自上的单向边连成一颗树。我们将这些边称为“虚边”
这个时候，Splay树只能维护它本身的节点，而不能照顾到由虚边连成的树。
由于要处理一段序列，我们就要得到一段序列。
下面是杨哲的论文的一段原话：
称一个点被访问过, 如果刚刚执行了对这个点的 ACCESS 操作.
如果结点 v 的子树中, 最后被访问的结点在子树 w 中, 这里 w 是 v 的儿子, 那么就称 w 是 v 的 Pre-
ferred Child. 如果最后被访问过的结点就是 v 本身, 那么它没有 Preferred Child. 每个点到它的 Preferred
Child 的边称作 Preferred Edge. 由 Preferred Edge 连接成的不可再延伸的路径称为 Preferred Path.
这样, 整棵树就被划分成了若干条 Preferred Path. 对每条 Preferred Path, 用这条路上的点的深度作
为关键字, 用一棵平衡树来维护它(在这棵平衡树中, 每个点的左子树中的点, 都在 Preferred Path 中这个点
的上方; 右子树中的点, 都在 Preferred Path 中这个点的下方). 需要注意的是, 这种平衡树必须支持分离与
合并. 这里, 我们选择 Splay Tree 作为这个平衡树的数据结构. 我们把这棵平衡树称为一棵 Auxiliary Tree.
知道了树 T 分解成的这若干条 Preferred Path, 我们只需要再知道这些路径之间的连接关系, 就可以表
示出这棵树 T. 用 Path Parent 来记录每棵 Auxiliary Tree 对应的 Preferred Path 中的最高点的父亲结点,
如果这个 Preferred Path 的最高点就是根结点, 那么令这棵 Auxiliary Tree 的 Path Parent 为 null.
Link-Cut Trees 就是将要维护的森林中的每棵树 T 表示为若干个 Auxiliary Tree, 并通过 Path
Parent 将这些 Auxiliary Tree 连接起来的数据结构.
通过上述的Access操作，我们就可以得到一段从任意点到根的序列，而通过Splay我们又可以将任意点变成根！
同时使用Splay我们可以很轻松地维护点的信息。
从这里似乎看到了LCT的核心思路了。
考虑核心的操作Access:
node *Access (node *u) { node *v = NIL; for (; u != NIL; u = u->par) { Splay (u); u->Ch[1] = v; update (v = u); } return v;}
这样每次将当前Splay树连接到虚边连接的上一颗Splay树的根的右子树，就保证了Splay树的二叉树性质，同时对于所有指向儿子的点中，在u到根这个序列中，左儿子的深度总是小于父亲，右儿子的深度总是大于父亲。
正是这个关键的性质可以让我们实现我们需要的功能。
首先第一个想到的自然是找到一个点的根，只需要不断往左子树找就好了
node *getroot (node *x) { for (x = Access (x); clear (x), x->Ch[0] != NIL; x = x->Ch[0]); return x;}
第二个是要让一个结点x变成新的根，显然做过Access后，在序列 根->x中根在Splay树的最左，x在Splay树的最右，此时只要将Splay树的根（注意区分这两个根）的左右子树交换位置，便让x成为了新的根，于是我们只要打上一个交换标记就好了
inline void evert (node *x) { Access (x)->rev ^= 1; Splay (x);}
在打完标记后要让x旋转至根更新Splay树
下面要实现树的合并。要在不同的两颗树的两个结点u，v间连接一条边，那么先要让其中一个点成为根，用虚边连另外一个点，再用Access将虚边变成实边就好了
inline void link (node *x, node *y) { evert (x); x->par = y; Access (x);}
同样树的分离也是一样，先然其中一个结点x成为根，选取y到x的序列成为一颗Splay树，这个时候再将y旋转至根，那么显然它的左子树包含了除了y的其它点，将它们分离即可
inline void cut (node *x, node *y) { evert (x); Access (y); Splay (y); y->Ch[0]->par = NIL; y->Ch[0] = NIL; update (y);}
如果要对一段序列进行操作，例如对树上x到y的路径上的点进行操作。先让x成为根，选取y到x的路径上的点和边做一颗Splay树，将y旋转至根（更新Splay树），将标记传给y就好了
inline void modify (node *x, node *y, int w) { evert (x); Access (y), Splay (y); _inc (y, w);}
查询只要同修改一样，只要直接返回我们需要的值就好了。
下面是一些例题：
1.HDU 4010
只需要将上述操作按要求调用就行了，模板题 ------ 题解
2.BZOJ 2002
装置从0开始
第i个装置能到达第i + ki个装置，意味着i的父亲是i + ki，如果i + ki 大于等于N，它的父亲就是N，这样即询问树上某个点到N 的距离，即由这点到n的Splay树的节点个数-1；
#include <iostream>#include <cstdio>using namespace std;const int MAXN = 200009;struct node { int sum; bool rev; node *par, *ch[2]; node() {sum = 0, rev = 0, par = ch[0] = ch[1] = 0;} node (int a) : sum (a) {rev = 0, par = ch[0] = ch[1] = 0;}} dt[MAXN], nil (0), *NIL = &nil;struct LinkcutTree { inline void update (node * x) { x->sum = x->ch[0]->sum + x->ch[1]->sum + 1; } void Rotate (node *x) { node *p = x->par, *g = p->par; int c = p->ch[0] == x; //0左旋，1右旋 p->ch[c ^ 1] = x->ch[c]; if (x->ch[c] != NIL) x->ch[c]->par = p; x->par = g; if (g->ch[0] == p) g->ch[0] = x; else if (g->ch[1] == p) g->ch[1] = x; x->ch[c] = p; p->par = x; update (p); } //将x旋转至x所在Splay树的根 void Splay (node *x) { node *p, *g; while ( (p = x->par) != NIL && (p->ch[0] == x || p->ch[1] == x) ) { if ( (g = x->par) != NIL && (p->ch[0] == x || p->ch[1] == x) ) { Rotate (x); } else { if ( (g->ch[1] == p) == (p->ch[1] == x) ) Rotate (p), Rotate (x); else Rotate (x), Rotate (x); } } update (x); } //获取从u到根的一段 node *Access (node *u) { node *v = NIL; for (; u != NIL; u = u->par) { Splay (u); u->ch[1] = v; update (v = u); } return v; }} LCT;int n, m;int f[MAXN], vis[MAXN];int main() { scanf ("%d", &n); for (int i = 0; i < n; i++) scanf ("%d", &f[i]); for (int i = 0; i <= n; i++) { dt[i].sum = 1, dt[i].rev = 0; dt[i].par = dt[i].ch[0] = dt[i].ch[1] = NIL; int t = i + f[i] < n ? i + f[i] : n; if(i!=n) dt[i].par = dt + t; } scanf ("%d", &m); for (int i = 1, cmd, x, k; i <= m; i++) { scanf ("%d %d", &cmd, &x); node * const tem = dt + x; if (cmd == 1) { LCT.Access (tem); LCT.Splay(tem); printf ("%d\n", tem->sum-1); } else { scanf ("%d", &k); LCT.Splay (tem); tem->ch[0]->par = tem->par; tem->ch[0] = NIL; tem->par = dt + (x + k < n ? x + k : n); } }}
3.BZOJ 2243
维护cl,cr,sum分别表示最左边的颜色，最右边的颜色，和颜色段数。
每个节点x的相邻的两个节点的颜色就可以由 x->ch[0]->cr 和x->ch[1]->cl 得到
颜色段数也可以由左右儿子得到
要注意的是，在打上翻转标记后cl和cr也要交换
#include <iostream>#include <cstdio>using namespace std;const int MAXN = 100009;struct node { //本身的颜色，最左边节点的颜色，最右边节点的颜色，颜色段数 int color, cl, cr, sum, cover; bool rev; node *par, *ch[2]; inline void cov (int x) { cover = cr = cl = color = x, sum = 1; } inline void re() { swap (cl, cr); rev ^= 1; }} dt[MAXN], *NIL = dt;struct LinkcutTree { inline void clear (node *const x) { if (x == NIL) return ; if (x->rev) { swap (x->ch[0], x->ch[1]); x->ch[0]->re(); x->ch[1]->re(); x->rev = 0; } if (x->cover) { if (x->ch[0] != NIL) x->ch[0]->cov (x->cover); if (x->ch[1] != NIL) x->ch[1]->cov (x->cover); x->cover = 0; } } inline void update (node * x) { if (x->ch[0] != NIL) x->cl = x->ch[0]->cl; else x->cl = x->color; if (x->ch[1] != NIL) x->cr = x->ch[1]->cr; else x->cr = x->color; x->sum = 1; if (x->ch[0] != NIL) { x->sum += x->ch[0]->sum; if (x->ch[0]->cr == x->color) --x->sum; } if (x->ch[1] != NIL) { x->sum += x->ch[1]->sum; if (x->ch[1]->cl == x->color) --x->sum; } } void Rotate (node *x) { node *p = x->par, *g = p->par; int c = p->ch[0] == x; //0左旋，1右旋 p->ch[c ^ 1] = x->ch[c]; if (x->ch[c] != NIL) x->ch[c]->par = p; x->par = g; if (g->ch[0] == p) g->ch[0] = x; else if (g->ch[1] == p) g->ch[1] = x; x->ch[c] = p; p->par = x; update (p); } void Splay (node *x) { node *p, *g; clear (x); while ( (p = x->par) != NIL && (p->ch[0] == x || p->ch[1] == x) ) { if ( (g = p->par) != NIL && (g->ch[0] == p || g->ch[1] == p) ) { clear (g), clear (p), clear (x); if ( (g->ch[1] == p) == (p->ch[1] == x) ) Rotate (p), Rotate (x); else Rotate (x), Rotate (x); } else { clear (p), clear (x); Rotate (x); } } update (x); } node *Access (node *u) { node *v = NIL; for (; u != NIL; u = u->par) { Splay (u); u->ch[1] = v; update (v = u); } return v; } inline void evert (node *x) { Access (x)->re(); Splay (x); } inline void link (node *x, node *y) { evert (x); x->par = y; Access (x); } inline int query (node *x, node *y) { evert (x); Access (y), Splay (y); return y->sum; } inline void modify (node *x, node *y, int w) { evert (x); Access (y), Splay (y); y->cov (w); }} LCT;int n, m;int main() { scanf ("%d %d", &n, &m); for (int i = 1, x; i <= n; i++) { scanf ("%d", &x); dt[i].par = dt[i].ch[0] = dt[i].ch[1] = NIL; dt[i].cover =0, dt[i].sum = 1; dt[i].cl = dt[i].cr = dt[i].color = x+1; } for (int i = 1, x, y; i < n; ++i) { scanf ("%d %d", &x, &y); LCT.link (dt + x, dt + y); } char cmd; for (int i = 1, u, v, k; i <= m; i++) { scanf ("\n%c %d %d", &cmd, &u, &v); if (cmd == ‘Q‘) printf ("%d\n", LCT.query (dt + u, dt + v) ); else if (cmd == ‘C‘) { scanf ("%d", &k); LCT.modify (dt + v, dt + u, k+1); } } return 0;}
4.BZOJ 2631
重点在于处理加和乘的共存问题
乘的时候所有值都要乘，加的时候sum要算上Splay树所有节点，中间值会爆INT
/* BZOJ 2631 LCT 需要的操作 路径权值 + * 处理+和*的共存*/#include <iostream>#include <cstdio>#define ll long longusing namespace std;const int MAXN = 100009, mod = 51061;struct node { int val, sum, inc, mtp,cnt; bool rev; node *par, *ch[2];} dt[MAXN], *NIL = dt;struct LinkcutTree { inline void _inc (node * x, int inc) { if (x == NIL) return; x->inc=(x->inc + inc)%mod; x->val=(x->val + inc)%mod; x->sum=(x->sum + ((ll)inc*x->cnt)%mod)%mod; } inline void _mtp (node *x, int mtp) { if (x == NIL) return; x->inc=((ll)x->inc * mtp)%mod; x->val=((ll)x->val * mtp)%mod; x->sum=((ll)x->sum*mtp)%mod; x->mtp=((ll)x->mtp*mtp)%mod; } inline void clear (node *const x) { if (x == NIL) return ; if (x->mtp!=1) { _mtp (x->ch[0], x->mtp); _mtp (x->ch[1], x->mtp); x->mtp = 1; } if (x->inc) { _inc (x->ch[0], x->inc); _inc (x->ch[1], x->inc); x->inc = 0; } if (x->rev) { swap (x->ch[0], x->ch[1]); x->ch[0]->rev ^= 1; x->ch[1]->rev ^= 1; x->rev = 0; } } inline void update (node * x) { x->sum=x->val,x->cnt=1; if(x->ch[0]!=NIL) { x->sum=(x->sum+ x->ch[0]->sum); x->cnt=(x->cnt+ x->ch[0]->cnt); } if(x->ch[1]!=NIL) { x->sum=(x->sum+ x->ch[1]->sum); x->cnt=(x->cnt+ x->ch[1]->cnt); } while(x->sum>=mod) x->sum-=mod; } void Rotate (node *x) { node *p = x->par, *g = p->par; int c = p->ch[0] == x; //0左旋，1右旋 p->ch[c ^ 1] = x->ch[c]; if (x->ch[c] != NIL) x->ch[c]->par = p; x->par = g; if (g->ch[0] == p) g->ch[0] = x; else if (g->ch[1] == p) g->ch[1] = x; x->ch[c] = p; p->par = x; update (p); } void Splay (node *x) { node *p, *g; clear (x); while ( (p = x->par) != NIL && (p->ch[0] == x || p->ch[1] == x) ) { if ( (g = p->par) != NIL && (g->ch[0] == p || g->ch[1] == p) ) { clear (g), clear (p), clear (x); if ( (g->ch[1] == p) == (p->ch[1] == x) ) Rotate (p), Rotate (x); else Rotate (x), Rotate (x); } else { clear (p), clear (x); Rotate (x); } } update (x); } node *Access (node *u) { node *v = NIL; for (; u != NIL; u = u->par) { Splay (u); u->ch[1] = v; update (v = u); } return v; } inline void evert (node *x) { Access (x)->rev ^= 1;Splay (x); } inline void link (node *x, node *y) { evert (x);x->par = y;Access (x); } inline void cut (node *x, node *y) { evert (x);Access (y);Splay (y); x=y->ch[0]->par = NIL; update (y); } inline int query (node *x, node *y) { evert (x);Access (y), Splay (y); return y->sum; } inline void modifyadd (node *x, node *y, int w) { evert (x);Access (y), Splay (y); _inc (y, w); } inline void modifymtp (node *x, node *y, int w) { evert (x);Access (y), Splay (y); _mtp (y, w); }} LCT;int n, q;int main() { scanf("%d %d",&n,&q); for (int i = 0; i <= n; i++) { dt[i].inc = 0; dt[i].mtp = dt[i].sum = dt[i].val = dt[i].cnt=1; dt[i].par = dt[i].ch[0] = dt[i].ch[1] = NIL; } for (int i = 1, x, y; i < n; i++) { scanf("%d %d",&x,&y); LCT.link (dt + x, dt + y); } char cmd; for (int i = 1, x, y, k, u, v; i <= q; i++) { scanf ("\n%c", &cmd); switch (cmd) { case ‘+‘: { scanf ("%d %d %d", &x, &y, &k); LCT.modifyadd (dt + x, dt + y, k); break; }; case ‘-‘: { scanf ("%d %d %d %d", &x, &y, &u, &v); LCT.cut (dt + x, dt + y); LCT.link (dt + u, dt + v); break; } case ‘*‘: { scanf ("%d %d %d", &x, &y, &k); LCT.modifymtp (dt + x, dt + y,k); break; } case ‘/‘: { scanf ("%d %d", &x, &y); printf ("%d\n", LCT.query (dt + x, dt + y) ); break; } } }}
动态树LCT小结