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);
- 判断是不是所在 Splay 的根结点:如果 u 的父亲没有儿子指针指向它,它就是所在 Splay 的根。
- 判断是所在 Splay 中左儿子还是右儿子的身份;
- Splay 的双旋:需要用到 isroot;
- 把旋转到所在 Splay 的根结点;
- 把到原树根结点的路径变成一条树链(不包括它之前树链的部分):维护两个指针分别指向当前结点和上一条链。每次把当前结点 Splay 到根,然后改变重链。
- 把变成原树的根:先 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 的时候。
修订记录
- 2020年5月18日 创建文章