LCT（Link Cut Tree）是一种动态维护树的结构变化以及相关信息的数据结构。

对 LCT 的理解

LCT 本质上是用 Splay 维护树链剖分：

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

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

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

具体来说，Splay 按照树链从深到浅的顺序维护树链的结点。而 LCT 就是一个 Splay 森林。

在实现过程中，我们一般使用父节点和子节点指针维护 Splay 的结果。

如果一对父子结点的指针是相互的，那么连接这两个点的边属于 Splay 上的边。

否则会出现父节点的子节点指针没有指向自己的情况，那么这条边就属于原树上的边。

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

LCT 的实现

接下来我们介绍一个函数式的 LCT 的代码实现。

通用函数

为了方便新节点的定义，我们封装一个函数：

int new_node(int v);

然后是老生常谈的信息合并与标记下传函数：

void pushup(int u);
void pushdown(int u);

为了支持原树根节点的变动，我们需要支持给 Splay 打翻转标记，表示这条树链的父子关系翻转。因此需要有一个打标记的函数：

void noderv(int u);

核心函数

接下来是有关 LCT 结构维护的核心函数。

为了代码的可读性，我们封装一个函数用于判断该结点是否是所在 Splay 的根节点：

bool isroot(int u);

同时封装一个函数用于获取这个结点是 Splay 上的左儿子还是右儿子：

bool get(int u);

接下来就是 Splay 的核心函数——旋转和伸展。但需要做一些小改动，比如判断当前结点是否是当前 Splay 的根：

void rotate(int u);
void splay(int u);

接下来是 LCT 的核心函数——贯通。它的作用是将结点到原树的根节点的路径变成一条树链，其他受影响的链会被截断一部分。

void access(int u);

然后是维护原树根节点变化的函数，它的作用是将结点变成原树的根节点：

void makeroot(int u);

常用函数

接下来是一些常用的函数，基于核心函数。但不是必需。

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);
  1. 检查是否连通；
  2. 在不连通的之间连一条边；
  3. 检查的边是否存在；
  4. 删除这条边（保证存在）

完整代码实现

/******************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 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 nodeassign(int u,int v){ val[u]=v, pushup(u); }
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 的时候。