LCT 初步

LCT（Link Cut Tree），可以动态维护树的结构变化以及路径信息。

对 LCT 的理解

LCT 可以理解为 Splay 维护树链剖分。Splay 指伸展树，是一种自适应的平衡树；树链剖分则是指广义地将树剖分为若干个链，而非狭义的轻重链剖分。

总体来说，LCT 可以解决以下的问题：

连接两个点；
删除某条边；
维护可合并的路径信息。

具体来说，Splay 按照树链从深到浅的顺序维护树链的结点。而 LCT 就是一个 Splay 森林。我们一般使用父节点和子节点指针可以维护 Splay 的特征。因此，如果某个指针它不符合 Splay 该有的特征（比如根结点的父节点指针是无意义的），那么这类指针就被用于维护树链之间的信息。

简单地说，LCT 的父节点指针在 Splay 内就是 Splay 的父节点指针，在 Splay 外（根节点的父节点指针）表示的就是这条树链的链顶的父节点指针。

通用函数

你需要实现以下函数：

int new_node(int v);
void pushup(int u);
void noderv(int u);
void pushdown(int u);

新建一个权值为 v 的结点，返回结点编号；
上传结点信息；
给一个结点打翻转标记；
标记下传（主要是翻转标记）。

核心函数

bool isroot(int u);
bool get(int u);
void rotate(int u);
void splay(int u);
void access(int u);
void makeroot(int u);

判断 $u$ 是不是所在 Splay 的根结点：如果 u 的父亲没有儿子指针指向它，它就是所在 Splay 的根。
判断 $u$ 是所在 Splay 中左儿子还是右儿子的身份；
Splay 的双旋：需要用到 isroot；
把 $u$ 旋转到所在 Splay 的根结点；
把 $u$ 到原树根结点的路径变成一条树链（不包括它之前树链的部分）：维护两个指针分别指向当前结点和上一条链。每次把当前结点 Splay 到根，然后改变重链。
把 $u$ 变成原树的根：先 access，然后打一个翻转标记。

常用函数

bool check_link(int x,int y);
void link(int x,int y);
bool check_edge(int x,int y);
void cut(int x,int y);

检查 x,y 是否连通；
在不连通的 x,y 之间连一条边；
检查 (x,y) 的边是否存在；
删除 (x,y) 这条边（保证存在）

在某些题目条件下不用写 1 和 3。

模板

/******************heading******************/
const int SZ=1e6+6;
int tot,ch[SZ][2],fa[SZ],val[SZ],sz[SZ],rv[SZ];

int new_node(int v){
    ++tot,ch[tot][0]=ch[tot][1]=fa[tot]=rv[tot]=0;
    sz[tot]=1,val[tot]=v,sxor[tot]=v;
    return tot;
}
void pushup(int u){
    sz[u]=sz[ch[u][0]]+sz[ch[u][1]]+1;
}
void noderv(int u){ if(u)rv[u]^=1; }
void nodeassign(int u,int v){ val[u]=v, pushup(u); }
void pushdown(int u){
    if(rv[u])swap(ch[u][0],ch[u][1]),noderv(ch[u][0]),noderv(ch[u][1]),rv[u]=0;
}
bool isroot(int u){return ch[fa[u]][0]!=u&&ch[fa[u]][1]!=u;}
bool get(int u){return ch[fa[u]][1]==u;}
void rotate(int u){
    int p=fa[u],pp=fa[p],k;
    pushdown(p),pushdown(u),k=get(u);//k 的赋值必须在 pushdown 后！
    if(!isroot(p))ch[pp][get(p)]=u;//!!!
    ch[p][k]=ch[u][!k], fa[ch[u][!k]]=p;
    ch[u][!k]=p,fa[p]=u, fa[u]=pp;
    pushup(p),pushup(u);
}
void splay(int u){
    pushdown(u);
    for(int p;p=fa[u],!isroot(u);rotate(u))
        if(!isroot(p))rotate(get(p)==get(u)?p:u);
}
void access(int u){
    for(int p=0;u;p=u,u=fa[u])splay(u),ch[u][1]=p,pushup(u);
}
void makeroot(int u){ access(u), splay(u), noderv(u); }
bool check_link(int x,int y){
    makeroot(x),access(y),splay(x),splay(y);
    return !(isroot(x)&&isroot(y));
}
void link(int x,int y){ makeroot(x), fa[x]=y; }
bool check_edge(int x,int y){
    if(!check_link(x,y))return 0;
    makeroot(x),access(y),splay(y);
    if(ch[y][0]!=x||ch[x][1])return 0;
    return 1;
}
void cut(int x,int y){
    makeroot(x),access(y),splay(y),ch[y][0]=fa[x]=0,pushup(y);
}
void assign(int x,int y){ splay(x), nodeassign(x,y); }
int query(int x,int y){ return makeroot(x), access(y),splay(y),sxor[y]; }

void print(){
    puts("---------------------------------");
    FOR(u,1,5)printf("u=%2d,lc=%2d,rc=%2d,sz=%2d,f=%2d,rv=%2d\n",
            u,ch[u][0],ch[u][1],sz[u],fa[u],rv[u]);
    puts("---------------------------------");
}
/*
 * 模板：Luogu3690
 * new_node: 新建权值为 v 的结点
 * pushup: 信息更新
 * pushdown: 标记下传，主要是翻转标记
 * noderv: 对某一个结点施加标记。
 *     LCT 的标记不同于线段树，必须在下传的时候再更新当前结点的信息。不然
 *     get 的时候会出锅
 * nodeassign: 模板题需要
 * isroot: 是否是所在 Splay 的根
 * get: 是 Splay 上左儿子还是右儿子
 * print: 调试函数
 * rotate: 双旋，注意与 Splay 的双旋不同，要判 fa[u] 是不是 root，不然 fa[fa[u]] 的
 *     儿子不能乱赋值
 * splay: 把当前结点旋转到当前 Splay 的根结点，要用到 isroot 函数。一开始
 *     先 pushdown。
 * access: 把当前结点到根的路径连成一个 Splay，注意这个 Splay 只包含当前结点
 *     到根这段路径上的点，不包括当前结点子树的那一段（非到叶结点的树链）
 *     access 完之后这个点不一定是所在 splay 的根，需要手动 splay 一下
 * makeroot: 把当前结点变成原树的根，这个结点也会顺便变成所在 Splay 的根。
 * check_link: 判断两个点是否连通。
 * link: 连接两个不连通的点
 * check_edge: 判断两个点是否直连通（有没有边）
 * cut: 删掉 (x,y) 的边。
 * assign: 模板题需要
 * query: 模板题需要
 */

BZOJ 2631

维护 Link/Cut，链加 / 乘 / 求和

对于 Tag 的维护，除了翻转 Tag 是在修改的时候打标记，下传的时候更新当前结点状态；其他标记都是在修改的时候打标记顺便更新该结点信息，在下传的时候更新子节点信息（与线段树相同）

代码

维护虚儿子信息

链上信息可以 Splay 维护。对于虚儿子的信息，我们可以使用 set 维护。那么就只需要在改变实儿子的时候更新这部分信息。也就是在 access，link 和 cut 的时候。

文章目录