\(\text{Link Cut Tree}\) 学习笔记
应用对象
在不改变树形态的前提下，树上求和求最值问题可以用树链剖分，树上统计问题可以用树分治。
而当出现连边断边的操作时，数的形态会发生改变，上述方法不再适用。而 \(\text{LCT}\) 就是解决动态树问题的工具。
初步定义
虚实链剖分：类比轻重链剖分，每个节点向一个儿子连出一条实边，其余儿子连出一条虚边，实边构成一条实链。用一棵 \(\text{Splay}\) 对应维护每一个实链，\(\text{Splay}\) 内部关键字为深度，也即其中序遍历是一条从上到下的实链。
现在得到了 \(\text{Splay}\) 森林，对于连通的树，我们将一个虚边的儿子（显然这个儿子一定是实链的链顶）在 \(\text{Splay}\) 的父亲定义为其在树上的父亲，而这个父亲不记录这些虚儿子。
大体感知：虚实链剖分，实链用 \(\text{Splay}\) 维护，每个链顶记录一下其父亲。
函数实现
\(\text{rotate(x)}\) 以及 \(\text{splay(x)}\)
大体与普通平衡树相同，有两点注意在后面提到。
\(\text{access(x)}\)
最关键的函数，目的是让当前树的根与 \(x\) 在同一个 \(\text{Splay}\) 中，也就是将这条根链调整为实链。
这里需要进行三步操作，设当前操作点为 \(x\)：
- 将 \(x\) 旋转至所在 \(\text{Splay}\) 的根，即作为链顶。
- 将当前操作点的右儿子修改为上一个操作点。（由于虚边只记录父亲，因此不需要对虚边对应儿子进行修改。）
- 记录当前操作点，下一个操作点为这个操作点的父亲。（\(\text{Splay}\) 旋转至根代表着旋转到了链顶，也就是说，无论根是谁，根的父亲始终是这条实链链顶的父亲。）
这里要注意，我们保证进行这样一系列的操作后，这条根链是完整的实链，也就是 \(x\) 如果有原树上的儿子也不会作为实儿子。
\(\text{makeroot(x)}\)
将 \(x\) 作为当前树的根，首先进行 \(\text{access(x)}\) 操作，使得 \(x\) 与根在同一实链当中，接下来将 \(x\) 旋转至根，此时由于 \(x\) 在平衡树中为中序遍历最后一个元素，因此要让 \(x\) 作为根则需要将中序遍历提到最前，直接平衡树全局翻转，打一个标记。
\(\text{findroot(x)}\)
找到 \(x\) 所在原树的根，依旧是 \(\text{access(x)}\) 之后找到中序遍历最靠前的节点即可。
\(\text{split(x,y)}\)
将 \((x,y)\) 这条链单独提出，实际上就是把 \(x\) 作为根之后再 \(\text{access(y)}\)。
\(\text{link(x,y)}\)
连边，将 \(x\) 作为根，之后虚边连到 \(y\) 上即可。
\(\text{cut(x,y)}\)
删边，注意这里删边的条件不止是连通，需要判断是不是直接相连，方法是判断中序遍历是不是相邻。
注意点
- 在 \(\text{Splay}\) 中，旋转的目标是当前平衡树的根，也就是当前实链的链顶，这意味着根实际上是有父亲的，且这个父亲不会记录虚儿子。而正常不加特判时，就会修改儿子信息，这是错误的。
- 翻转操作需要在改变形态前及时解决，具体是每次 \(\text{splay(x)}\) 前，先将根到 \(x\) 上每个节点的标记下传。
模板
点击查看代码
struct LinkCutTree{
int fa[maxn],ch[maxn][2],val[maxn],xorsum[maxn];
bool rev[maxn];
int st[maxn],top;
inline void push_up(int x){xorsum[x]=xorsum[ch[x][0]]^xorsum[ch[x][1]]^val[x];}
inline void push_down(int x){
if(rev[x]){
rev[ch[x][0]]^=1,rev[ch[x][1]]^=1;
swap(ch[x][0],ch[x][1]);
rev[x]=0;
}
}
inline bool isroot(int x){return (x!=ch[fa[x]][0])&&(x!=ch[fa[x]][1]);}
inline bool pdson(int x){return x==ch[fa[x]][1];}
inline void rotate(int x){
int y=fa[x],z=fa[y];
bool chk=pdson(x);
if(!isroot(y)) ch[z][pdson(y)]=x;
fa[x]=z;
ch[y][chk]=ch[x][chk^1],fa[ch[x][chk^1]]=y;
ch[x][chk^1]=y,fa[y]=x;
push_up(y),push_up(x);
}
inline void splay(int x){
top=0;
st[++top]=x;
for(int u=x;!isroot(u);u=fa[u]) st[++top]=fa[u];
for(int i=top;i>=1;--i) push_down(st[i]);
while(!isroot(x)){
int y=fa[x],z=fa[y];
if(!isroot(y)) rotate(pdson(x)==pdson(y)?y:x);
rotate(x);
}
}
inline void access(int x){
for(int tmp=0;x;tmp=x,x=fa[x]){
splay(x);
ch[x][1]=tmp;
push_up(x);
}
}
inline void makeroot(int x){
access(x);
splay(x);
rev[x]^=1;
}
inline int findroot(int x){
access(x);
splay(x);
while(ch[x][0]) x=ch[x][0];
return x;
}
inline void split(int x,int y){
makeroot(x);
access(y);
splay(y);
}
inline void link(int x,int y){
makeroot(x);
fa[x]=y;
}
inline void cut(int x,int y){
split(x,y);
if(ch[y][0]==x&&ch[x][1]==0) ch[y][0]=0,fa[x]=0;
}
inline void update(int x,int k){
access(x);
splay(x);
val[x]=k;
push_up(x);
}
}T;
小技巧
- 由于维护动态树，很多时候不能使用边权退化为子节点点权的方式处理，这时将 \((u,v,w)\) 建成 \((u,id)\) 与 \((id,v)\) 其中 \(id\) 点权为边权。
- \(\text{LCT}\) 可以维护动态加边图的最小生成树（同时也是最小瓶颈生成树），类似于判断静态一条边权值在什么范围内可以作为最小生成树边，只需要维护 \(\text{Splay}\) 内的最大边权以及最大边权来源，同样是要开节点表示边。
一些题
BZOJ-3514 Codechef MARCH14 GERALD07加强版
求 \([l,r]\) 中边组成的子图连通块个数。
按照顺序加边，假设 \(j\) 加入时已经连通，且最早加入的边为 \(i\)，那么如果 \(l>i,r<j\)，就一定是不连通的。
拓展一下，如果又有 \(k\) 顶替了 \(j\)，相当于形成了一个 \(i\to j\to k\) 的链，那么 \([l,r]\) 中有元素在链中就会连通，反之则不连通。
那么实际上就是求区间种类数（此类链个种类数），使用主席树，维护最新的生成树就是要用 \(\text{LCT}\) 了。