LCT(Link Cut Tree),可以动态维护树的结构变化以及路径信息。

对 LCT 的理解

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

总体来说,LCT 可以解决以下的问题:

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

具体来说,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);
  1. 新建一个权值为 v 的结点,返回结点编号;
  2. 上传结点信息;
  3. 给一个结点打翻转标记;
  4. 标记下传(主要是翻转标记)。

核心函数

bool isroot(int u);
bool get(int u);
void rotate(int u);
void splay(int u);
void access(int u);
void makeroot(int u);
  1. 判断是不是所在 Splay 的根结点:如果 u 的父亲没有儿子指针指向它,它就是所在 Splay 的根。
  2. 判断是所在 Splay 中左儿子还是右儿子的身份;
  3. Splay 的双旋:需要用到 isroot;
  4. 旋转到所在 Splay 的根结点;
  5. 到原树根结点的路径变成一条树链(不包括它之前树链的部分):维护两个指针分别指向当前结点和上一条链。每次把当前结点 Splay 到根,然后改变重链。
  6. 变成原树的根:先 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);
  1. 检查 x,y 是否连通;
  2. 在不连通的 x,y 之间连一条边;
  3. 检查 (x,y) 的边是否存在;
  4. 删除 (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 的时候。