从这里开始
动态树问题和Link Cut Tree
动态树问题是一类要求维护一个有根树森林，支持对树的分割, 合并等操作的问题。
Link Cut Tree（林可砍树？简称LCT）是解决这一类问题的一种数据结构。
一些无聊的定义
Link Cut Tree维护的是动态森林中每棵树的任意链剖分。
Preferred Child，每个点偏好的子节点，对于每个点，要么它没有，要么它只有一个。
Preferred Edge，连接每个点和它偏好的子节点的边，以下简称为实边。
相对地，对于非实边的边，以下简称为虚边。
Preferred Path，由Preferred Edge 连接成的不可再延伸的路径。以下简称为实链。特殊地，如果与一个点相连的所有边都是虚边，那么这一个点独自构成一条实链。
显然，所有实链覆盖所有的点。
对于每条实链，LCT用一颗Splay对节点按深度为关键字进行维护。
//接下来会默认读者能熟练地敲打Splay的板子
为了方便直接用Splay森林来维护。对于每棵Splay，它还需要维护它的维护的实链的顶端（深度最小的点）的父节点，这个记在根结点上。
access操作
access操作是将某个节点$x$到根的路径变为实链。
由图中可以看出，access操作可以看成以下几个操作的反复进行：
- 断掉当前实链中当前点和比它深的点之间的实边
- 合并当前实链和上一条实链
- 访问实链顶端的父节点
当当前点为空的时候结束，不存在上一条实链的时候它为空。
显然这样操作恰好将指定点到根的路径变为实链了。
void access(SplayNode *p) {
SplayNode* q = NULL;
while (p) {
splay(p);
q = p, p = p->fa;
}
}
换根操作
将一棵树的根变为指定点。
考虑换根操作的影响：
只是旧根到新根的路径被翻转了。那就先对新根执行access操作，然后打反转标记就好了。
void mkroot(SplayNode* node) {
access(node);
splay(node);
node->rev ^= ;
}
link和cut操作
link操作是连接两个不连通的点，cut操作是删除一条原有的边。
考虑link操作，将其中一个作为根然后向另一个点连接一条虚边即可。
考虑cut操作，将其中一个作为根，然后对另一个点做access操作，这样恰好根所在的Splay中的后继是另一个点，Splay树上断掉这条边即可。
void link(int u, int v) {
SplayNode* p = pool + u, *q = pool + v;
if(isConnected(p, q)) return ;
mkroot(q);
q->fa = p, splay(q);
}
void cut(int u, int v) {
SplayNode* p = pool + u, *q = pool + v;
mkroot(p);
access(q);
splay(q);
q->ch[] = p->fa = NULL;
}
例1 Cave 洞穴勘测
题目大意
给定一个动态森林，要求支持加边、删边和询问两点之间的连通性。
判断两点之间是否连通，等价于它们所在的树的根相同。
所以考虑如何找一个点所在树的根。
首先access这个点，然后把它伸展到根，然后暴力跳左子树就好了。
Code
/**
* bzoj
* Problem#2049
* Accepted
* Time: 1976ms
* Memory: 1500k
*/
#include <bits/stdc++.h>
using namespace std;
typedef bool boolean; typedef class SplayNode {
public:
boolean rev;
SplayNode *ch[];
SplayNode *fa; SplayNode():rev(), ch({NULL, NULL}), fa(NULL) { } boolean isRoot() {
if(fa == NULL) return true;
return fa->ch[] != this && fa->ch[] != this;
} void pushDown() {
swap(ch[], ch[]);
if(ch[]) ch[]->rev ^= ;
if(ch[]) ch[]->rev ^= ;
rev = ;
}
}SplayNode; typedef class LinkCutTree {
public:
SplayNode *pool; LinkCutTree():pool(NULL) { }
LinkCutTree(int n) {
pool = new SplayNode[(n + )];
} void rotate(SplayNode* node) {
SplayNode* fa = node->fa;
boolean aFlag = fa->isRoot();
int d = fa->ch[] == node;
fa->ch[d] = node->ch[d ^ ];
node->fa = fa->fa;
fa->fa = node;
node->ch[d ^ ] = fa;
if(fa->ch[d]) fa->ch[d]->fa = fa;
if(!aFlag) node->fa->ch[node->fa->ch[] == fa] = node;
} SplayNode* s[];
void splay(SplayNode* node) {
int top = ;
s[++ top] = node;
for (SplayNode* p = node; !p -> isRoot(); p = p->fa) s[++ top] = p -> fa;
for (int i = top; i; -- i) if (s[i] -> rev) s[i] -> pushDown();
while(!node->isRoot()) {
SplayNode *fa = node->fa, *ffa = fa->fa;
if(fa->isRoot()) {
rotate(node);
break;
}
int d1 = (fa->ch[] == node), d2 = ffa->ch[] == fa;
if(d1 == d2)
rotate(fa);
else
rotate(node);
rotate(node);
}
} SplayNode* findSplayRoot(SplayNode* node) {
access(node);
// while(node->fa) node = node->fa;
splay(node);
while(node->ch[]) node = node->ch[];
return node;
} void access(SplayNode* node) {
SplayNode* p = NULL;
do {
splay(node);
node->ch[] = p;
p = node;
node = node->fa;
} while (node);
} boolean isConnected(SplayNode* p, SplayNode* q) {
return findSplayRoot(p) == findSplayRoot(q);
} void mkroot(SplayNode* node) {
access(node);
splay(node);
node->rev ^= ;
} void link(int u, int v) {
SplayNode* p = pool + u, *q = pool + v;
if(isConnected(p, q)) return ;
mkroot(q);
q->fa = p, splay(q);
} void cut(int u, int v) {
SplayNode* p = pool + u, *q = pool + v;
mkroot(p);
access(q);
splay(q);
q->ch[] = p->fa = NULL;
} boolean isConnected(int u, int v) {
return isConnected(pool + u, pool + v);
}
}LinkCutTree; int n, m;
LinkCutTree lct;
char buf[];
int u, v;
inline void solve() {
scanf("%d%d", &n, &m);
lct = LinkCutTree(n);
while(m--) {
scanf("%s%d%d", buf, &u, &v);
switch(buf[]) {
case 'C':
lct.link(u, v);
break;
case 'D':
lct.cut(u, v);
break;
case 'Q':
puts((lct.isConnected(u, v)) ? ("Yes") : ("No"));
break;
}
}
} int main() {
solve();
return ;
}
时间复杂度证明
如果学习一个数据结构能证明它的时间复杂度那就再好不过了。
对于LCT的操作，基本上是access，然后加上某些$O(1)$的操作或者均摊$O(\log n)$的Splay操作。所以只需要证明access的时间复杂度是$O(\log n)$即可。
在开始证明前，你需要知道Splay的时间复杂度和一些常识性的东西。
定理1 对于操作splay(x)，设操作前$x$的子树大小为$siz[x]$，操作后的子树大小为$siz'[x]$，splay(x)的均摊时间复杂度小于等于$3(\log siz'[x] - \log siz[x]) + 1$
证明略去（其实是我不会）
下面一个是关于轻重链剖分的常识，证明可以看这篇随笔。
定理2 一条根节点到叶节点的路径上，轻边的条数不超过$\log_{2}n$条
然后还有一个需要证明的事情。
定理3 Preferred Child的改变次数均摊为$O(log_{2}n)$次
证明 因为每次Preferred Child的改变时会导致实边发生改变。所以考察实边改变的次数即可。
这一部分可以分为两种情况：
- 一条轻虚边被改为轻实边。
- 一条重虚边被改为重实边。
因为轻边总数不超过$\log_{2}n$条，所以第一部分的改变次数不超过$\log_{2}n$次。
考虑重虚边被改为重实边的情况。
考虑每一条重边，它从实变为虚，虚变为实的过程是交替进行的。所以它被改为实边的次数不会超过它从实边被改为虚边的次数加1。
当一条重实边被改为重虚边会导致一条轻虚边变为轻实边，同时我们证明了轻虚边变为轻实边的均摊次数不超过$O(log_{2}n)$，所以一条重虚边被改为重实边的次数也不超过$O(log_{2}n)$。
因此定理得证。
定理4 access的均摊时间复杂度为$O(log_{2}n)$
证明 设每次设为当前点的点依次为$v_{0}, v_{1}, v_{2},\cdots,v_{k}$。
那么有：
$\widehat{cost}\leqslant 3\left (\sum_{i = 1}^{k}\log siz[v_{i}] - \log siz[v_{i - 1}] + 1 \right ) + \log siz[v_{0}]$
所以化简后再根据定理3，可得：
$\widehat{cost}\leqslant 6\log{n}$
Link Cut Tree维护链上信息
对于有关边权的链上信息考虑为每条边建一个虚点。然后和它两端连边。
查询链上信息可以通过把一个点变为根，access另一个点后的splay中的信息就是这条链上的信息。
但是有些装逼爱好者觉得这样不能满足他们的欲望，想出了一种不用建虚点的方法。很开心的是细节超多，看到neither_nor的某道题写了200+行，想想得到结论——装逼是要有代价的。
这个方法的讲解：neither_nor神犇的博客
例2 魔法森林
题目大意
一张图有$n$个点，$m$条边，第$i$条边有两个边权$a_{i}$和$b_{i}$。定义从1号点走到$n$号点的代价是经过边的所有$a$边权的最大值加上所有$b$边权的最大值。
问从1号点走到$n$号点的最小代价。
高维问题常见思路是降维，因此考虑按照$a$边权排序，然后枚举。
假设图开始是空的，然后依次加入每一条边。
- 如果边的两端未连通，直接加就好了。
- 如果边的两端连通，那么会形成环。根据人生的经验和图论的哲理，可以知道，环是这两点在树上的简单路径再加上这一条边。那么找到换上$b$边权最大的一条边比较它和当前边的$b$边权。如果当前边的$b$边权更小，那么就把树上的那条边cut掉，然后把这条新边加上。
如果在某个时候1和$n$连通，就查询一下它们之间的简单路径中$a$边权和$b$边权的最大值就好了。
由于这里的“删边”不会改变连通性（因为马上你会加一条边），所以可以直接用并查集维护连通性。
Code
/**
* uoj
* Problem#3
* Accepted
* Time: 2287ms
* Memory: 11208k
*/
#include <bits/stdc++.h>
using namespace std;
typedef bool boolean; typedef class SplayNode {
public:
boolean rev;
int ea, eb, idx;
int ma, mb, ib;
SplayNode *ch[];
SplayNode *fa; SplayNode():rev(false), ea(), eb(), idx(), ma(), mb(), ib(), ch({NULL, NULL}), fa(NULL) { } void pushUp() {
ma = ea, mb = eb, ib = idx;
for (int i = ; i < ; i++)
if (ch[i]) {
(ch[i]->ma > ma) ? (ma = ch[i]->ma) : ();
(ch[i]->mb > mb) ? (mb = ch[i]->mb, ib = ch[i]->ib) : ();
}
} void pushDown() {
swap(ch[], ch[]);
if (ch[]) ch[]->rev ^= ;
if (ch[]) ch[]->rev ^= ;
rev = false;
} boolean isroot() {
return !fa || (fa->ch[] != this && fa->ch[] != this);
} int which() {
return (!isroot()) ? (fa->ch[] == this) : (-);
}
}SplayNode; typedef class LinkCutTree {
public:
SplayNode* pool;
SplayNode** s;
int top, n; LinkCutTree() { }
LinkCutTree(int n, int m):n(n) {
pool = new SplayNode[(n + m + )];
s = new SplayNode*[(n + m + )];
} void rotate(SplayNode* p) {
int d = p->which(), df = p->fa->which();
SplayNode* fa = p->fa, *ffa = fa->fa, *ls = p->ch[d ^ ];
fa->ch[d] = ls, (ls) ? (ls->fa = fa) : ();
p->fa = ffa, (~df) ? (ffa->ch[df] = p) : ();
p->ch[d ^ ] = fa, fa->fa = p;
fa->pushUp(), p->pushUp();
} void splay(SplayNode* p) {
SplayNode *np = p;
for (top = ; s[++top] = np, !np->isroot(); np = np->fa);
for ( ; top; top--)
if (s[top]->rev)
s[top]->pushDown();
for ( ; !p->isroot(); rotate(p))
if (!p->fa->isroot())
rotate((p->which() == p->fa->which()) ? (p->fa) : (p));
} void access(SplayNode *p) {
SplayNode* q = NULL;
while (p) {
splay(p);
p->ch[] = q;
p->pushUp();
q = p, p = p->fa;
}
} void mkroot(SplayNode *p) {
access(p);
splay(p);
p->rev ^= ;
} void link(SplayNode* p, SplayNode* q) {
mkroot(q);
q->fa = p;
} void cut(SplayNode* p, SplayNode* q) {
mkroot(p);
access(q);
p->ch[] = q->fa = NULL;
p->pushUp();
} SplayNode* query(int u, int v) {
SplayNode* p = pool + u, *q = pool + v;
mkroot(p), access(q);
splay(p);
return p;
} void link(int u, int v, int a, int b, int idx) {
SplayNode* p = pool + u, *q = pool + v, *es = pool + n + idx;
es->ea = es->ma = a, es->eb = es->mb = b, es->ib = es->idx = idx;
link(p, es), link(es, q);
} void cut(int u, int v, int idx) {
SplayNode *p = pool + u, *q = pool + v, *es = pool + n + idx;
cut(p, es), cut(es, q);
} void debugOut(SplayNode* p) {
if (!p) return;
fprintf(stderr, "%d (fa: %d, ea: %d, eb: %d, ma: %d, mb: %d, idx: %d, ib: %d, flag: %d) {", p - pool, (!p->fa) ? () : (p->fa - pool), p->ea, p->eb, p->ma, p->mb, p->idx, p->ib, p->rev);
debugOut(p->ch[]);
fprintf(stderr, ", ");
debugOut(p->ch[]);
fprintf(stderr, "}");
} void debugOut() {
fprintf(stderr, "--------------------\n");
for (int i = ; i <= ; i++)
if (pool[i].isroot())
debugOut(pool + i), fprintf(stderr, "\n");
}
}LinkCutTree; typedef class Edge {
public:
int u, v, a, b; boolean operator < (Edge b) const {
return a < b.a;
}
}Edge; int n, m;
int res = ;
int* f;
Edge* es;
LinkCutTree lct; int find ( int x ) {
while ( x != f [x] ) x = f [x] = f [f [x]] ;
return x ;
} inline void init() {
scanf("%d%d", &n, &m);
f = new int[(n + )];
es = new Edge[(m + )];
lct = LinkCutTree(n, m);
for (int i = ; i <= n; i++)
f [i] = i ;
for (int i = ; i <= m; i++)
scanf("%d%d%d%d", &es[i].u, &es[i].v, &es[i].a, &es[i].b);
} inline void solve() {
SplayNode* p;
sort(es + , es + m + );
for (int i = , u, v, a, b; i <= m; i++) {
u = es[i].u, v = es[i].v, a = es[i].a, b = es[i].b;
if (u == v) continue;
if (find(u) != find(v)) {
lct.link(u, v, a, b, i);//, cerr << u << " " << v << endl;
f [find ( u )] = find ( v ) ;
}
else {
// cerr << "R:" << u << " " << v << endl;
p = lct.query(u, v);
if (p->mb > b) {
lct.cut(es[p->ib].u, es[p->ib].v, p->ib);
lct.link(u, v, a, b, i);
}
}
if (find ( ) == find (n)) {
p = lct.query(, n);
res = min(res, p->ma + p->mb);
// cerr << "Q" << endl;
}
// lct.debugOut();
}
printf("%d\n", (res == ) ? (-) : (res));
} int main() {
srand();
init();
solve();
return ;
}
Link Cut Tree维护子树信息
首先来说说一些无聊的定义。
众所周知，LCT维护的是一个动态森林的链剖分。
定义一个点的LCT子树是这个点在Splay上的子树。
所以LCT子树可能并不是原树中的子树，它可能包含这个点的祖先。
一个点的所有虚子树是在Splay中所有与它通过虚边相连的点的LCT子树。
一个点的所有实子树是在Splay中它的左右子树。
因此一个点的LCT子树等于它的所有虚子树加上它的所有实子树和它自己。
某个很有用的性质 将一个点access后，它的虚子树信息再加上它自己的信息就是它的在原树中的子树信息。
因为access这个点之后它就没有Preferred Child，它的所有子节点都和它通过虚边相连。它的子节点的LCT子树不包含后代，所以恰好是原树中的子树信息。
考虑什么时候虚子树信息会改变：
- 当access一个点后
- 当进行link和cut操作时
情况1很好处理，断开一条实边的时候加上它的LCT子树信息，添加一条实边的时候减去它的LCT子树信息。
看起来现在需要维护LCT子树信息，也就是说修改后还需要将信息上传。
但是access进行断边的时候能够保证当前点是Splay的根，所以通常不用上传任何信息（因为通常它的LCT子树信息不会改变）。
考虑link操作，我们会添加一条虚边，它会改变一个点的子树信息以及它的祖先的子树信息。
所以我们先access它，然后把它伸展到根，于是就巧妙地避开了更新祖先的子树信息。
继续考虑cut操作，我们会断掉1条边，可以用同样的方法进行处理。
注意事项
- Splay的形态发生改变时会改变LCT子树信息但是不会改变虚子树信息
- 发生虚实边的改变时才会导致虚子树信息发生改变
- 修改时要考虑信息上传的问题，如果难以上传可以考虑避开上传，或者直接进行链上修改。
例3 大融合
题目大意
维护一个动态森林，要求支持
- 添加一条边
- 询问经过一条边的所有简单路径数
假如是一个静态森林，那么如果处理询问操作？
这条边会把树分成两部分，对吧？答案是这两个部分的点数的乘积。
考虑如何在动态森林中维护子树大小，还是很显然的。
那么如何算答案？
把其中一个变成根，然后就可以计算两部分的点数了。
Code
/**
* bzoj
* Problem#4530
* Accepted
* Time: 1124ms
* Memory: 3488k
*/
#include <bits/stdc++.h>
#ifndef WIN32
#define Auto "%lld"
#else
#define Auto "%I64d"
#endif
using namespace std;
typedef bool boolean; #define ll long long typedef class SplayNode {
public:
boolean rev;
int ls, vs;
SplayNode* ch[];
SplayNode* fa; SplayNode():rev(false), ls(), vs(), ch({NULL, NULL}), fa(NULL) { } void pushUp() {
ls = + vs;
if (ch[]) ls += ch[]->ls;
if (ch[]) ls += ch[]->ls;
} void pushDown() {
swap(ch[], ch[]);
if (ch[]) ch[]->rev ^= ;
if (ch[]) ch[]->rev ^= ;
rev = false;
} boolean isRoot() {
if (!fa) return true;
return fa->ch[] != this && fa->ch[] != this;
}
}SplayNode; typedef class LinkCutTree {
public:
int top;
SplayNode* pool;
SplayNode** s; LinkCutTree():pool(NULL), s(NULL) { }
LinkCutTree(int n):top() {
pool = new SplayNode[(n + )];
s = new SplayNode*[(n + )];
} void rotate(SplayNode *p) {
int d = (p->fa->ch[] == p), d1 = (p->fa->fa) ? (p->fa->fa->ch[] == p->fa) : (-);
SplayNode *fa = p->fa, *ffa = fa->fa, *ls = p->ch[d ^ ];
boolean sign = fa->isRoot();
p->ch[d ^ ] = fa, fa->fa = p;
fa->ch[d] = ls, (ls) ? (ls->fa = fa) : ();
p->fa = ffa, (!sign && ~d1) ? (ffa->ch[d1] = p) : ();
fa->pushUp(), p->pushUp();
} void splay(SplayNode* p) {
SplayNode *np = p, *fp = p->fa;
for (top = ; s[++top] = np, !np->isRoot(); np = np->fa);
for (; top; top--)
if (s[top]->rev)
s[top]->pushDown();
for (; !p->isRoot(); rotate(p), fp = p->fa)
if (!fp->isRoot())
rotate(((fp->fa->ch[] == fp) == (fp->ch[] == p)) ? (fp) : (p));
} void access(SplayNode *p) {
SplayNode *q = NULL;
while (p) {
splay(p);
p->vs += ((p->ch[]) ? (p->ch[]->ls) : ());
p->vs -= ((q) ? (q->ls) : ());
p->ch[] = q;
p->pushUp();
q = p, p = p->fa;
}
} void mkroot(SplayNode *p) {
access(p);
splay(p);
p->rev ^= ;
} void link(int u, int v) {
SplayNode *a = pool + u, *b = pool + v;
mkroot(b);
access(a);
splay(a);
b->fa = a;
a->vs += b->ls;
a->pushUp();
} SplayNode* findPre(SplayNode* p) {
splay(p);
p = p->ch[];
while (p) {
if (p->rev) p->pushDown();
if (!p->ch[]) break;
p = p->ch[];
}
return p;
} ll query(int u, int v) {
SplayNode *p = pool + u, *q = pool + v;
mkroot(p);
access(q);
splay(p);
int s1 = q->vs + , s2 = p->ls;
return s1 * 1ll * (s2 - s1);
}
}LinkCutTree; int n, m;
LinkCutTree lct; inline void init() {
scanf("%d%d", &n, &m);
lct = LinkCutTree(n);
} inline void solve() {
char s[];
int u, v;
while (m--) {
scanf("%s%d%d", s, &u, &v);
if (s[] == 'A')
lct.link(u, v);
else
printf(Auto"\n", lct.query(u, v));
}
} int main() {
init();
solve();
return ;
}
小结
LCT的时间复杂度虽然只带一个log，但是算上常数没有两个log的树链剖分快，而且树链剖分好写好调，LCT细节繁杂，所以尽量挖掘题目性质，避免盲目使用LCT（比如有些题可以线段数分治或者离线树剖就可以过）。
LCT维护链的常用套路：将一个点设为根，将另一个点access。
提取LCT中链、子树信息的时候要考虑是否提取到的信息是否是想要的（比如我经常忘记先splay）
LCT中splay操作时，最好先进行从上往下进行pushDown。我不知道为什么在旋转操作中pushDown会在一些题目蜜汁T掉。
特别感谢
ZJC
Doggu
MaxMercer
参考资料
neither_nor的讲课ppt
《QTREE解法的一些研究》 杨哲