Link-Cut-Tree

Tags：数据结构

更好阅读体验：https://www.zybuluo.com/xzyxzy/note/1027479

一、概述

$LCT$，动态树的一种，又可以$link$又可以$cut$

引用：http://www.cnblogs.com/zhoushuyu/p/8137553.html

二、题目

三、支持操作

I 维护联通性

维护两点联通性，较易，例题：Cave 洞穴勘测

II 维护树链信息

正是由于这个LCT可以代替树链剖分的关于链的操作（关于子树信息是无法做到的，感谢@cjfdf斧正「2018.2.25」）

运用$split$操作把$x$到$y$这条链抠出来操作

例题：【模板】Link Cut Tree

这是$LCT$的最大作用之一，几乎在每道题中都有体现

PS:树剖的常数小且相对容易调试，建议能写树剖则写（如“初步”的后三题，没有删边操作）

III 维护生成树

例题：“初步”中水管局长到温暖会指引我们前行

这里较为重要，理解需要时间

引入：一条路径的权值定义为该路径上所有边的边权最大值，问x到y的所有路径中，路径权值最小的路径的权值是多少，要求支持加边或删边，$O(nlogn)$求解

解决：

要求支持加边，那么每构成一个环就把环内最大边删掉，若支持删边则离线逆序处理
化边为点，每个$splay$节点记录${fa,ch[2],rev,val,id,d1,d2}$，分别表示父亲，孩子，翻转标记，该点权值（如果该点为边则为边权，如果为点那么最大生成树中值为$inf$，最小生成树中值为$-inf$），在该节点所在的$splay$中、以该节点为根的子树中权值最大（小）的点的编号，（若该节点表示边）与该边相连的两个点的编号
加入一条边$(x,y)$的时候，判断$x,y$是否联通，若联通，$split(x,y)$，判断这条路径上的边权最大值（最小值）和所加入的边的边权的关系，再决定$continue$或$cut$再$link$

pushup片段

int Getmax(int x,int y){return t[x].val>t[y].val?x:y;}

void pushup(int x){t[x].id=Getmax(x,Getmax(t[lc].id,t[rc].id));}

IV 维护边双联通分量

例题：星球联盟、长跑

这里难懂，慢慢体会

解释：

边双联通，其实就是说有两条不想交的路径可以到达

这里表述也不是特别清楚，这两道题的意思是————把环缩点

两道题一句话题意：求x，y路径上点(超级点)的siz(val)之和

实现：

类似于$Tarjan$缩点，遇到环，暴力DFS把所有点指向一个标志点

在之后凡要用到一个点就x=f[x]

相当于踏入这个环就改成踏进这个超级点

能够保证$DFS$总复杂度为$O(n)$（虽然星球联盟暴力不缩点也可以过）

核心代码片段

//并查集find

int find(int x){return f[x]==x?x:f[x]=find(f[x]);}

//读进来的时候就改成超级点

int x=read(),y=read();x=find(x);y=find(y);

//goal为超级点

void DFS(int x,int goal)

{

    if(lc)DFS(lc,goal);

    if(rc)DFS(rc,goal);

    if(x!=goal){f[x]=goal;siz[goal]+=siz[x];}

}

//每次访问点的时候都访问其find

void rotate(int x)

{

    int y=find(t[x].fa),z=find(t[y].fa);

    ...

}

void Access(int x){for(int y=0;x;y=x,x=find(t[x].fa)){splay(x);t[x].ch[1]=y;pushup(x);}}

...

V 维护原图信息

例题：大融合、动态树

难懂，烦请细细品味

解释：

先知道这几个名词和性质：
A、实儿子：$x$在$splay$中的儿子
B、虚儿子：与$x$在原图中有直接连边但和$x$不在同一棵$splay$中
C、若在原图中$x$是$y$的父亲，且$x$，$y$不在同一棵$splay$中，那么$y$所在的$splay$的根的父亲指向$x$
再知道这几个要点：
A、$x$与其实儿子在原图中不一定有直接连边
B、上文讲到的维护树链的信息都是维护实儿子的信息
C、$x$的实儿子信息包括了实儿子的虚儿子和实儿子的实儿子
那么在原图中的子树信息就可以这样求：Access(x)后返回x虚儿子的信息

实现

$Access$的目的是使得x没有实儿子，那么虚儿子便是原子树的信息

因为$x$的实儿子中有可能有点是原图中的儿子，那么只算虚儿子会算不全，都算会多算

以维护$siz$为例：

记录每个点的$Rs$表示虚儿子信息，$siz$表示实儿子和虚儿子的信息

需要改动的地方只有$Access$和$link$

核心代码片段

//要改变的两个操作

void Access(int x)

{

	for(int y=0;x;y=x,x=t[x].fa)

	{

		splay(x);

		t[x].Rs=t[x].Rs+t[rc].siz-t[y].siz;//把一个实儿子变成虚儿子要+t[rx].siz,把一个虚儿子变成实儿子要-t[y].siz

		rc=y;pushup(x);

	}

}

void link(int x,int y){makeroot(x);makeroot(y);t[x].fa=y;t[y].Rs+=t[x].siz;}//link要makeroot(y)因为连上x后y到该棵splay的根都有影响

注意的是这里调用的都是$t[son].siz$也就是$son$这棵子树所有的值，而不是这个点的值！！

由于这个原因共价大爷游长沙调试了半个小时

四、做题经验

1、辨别

如何看出一道题要用$LCT$————动态加/删边！

2、常数

只有加边操作时，维护两点是否联通请用并查集

$findroot$在以下题目会TLE：温暖会指引我们前行、长跑

3、所谓奇技淫巧

\[\sum_{l<=i<=r}deep(lca(i,z))
\]

这是[LNOI2014]LCA的题面，方法是在这个区间内每个点到根的路径+1,统计z到根的路径之和即为答案，处理区间时，很多时候用$$Ans(L,R)=Ans(R)-Ans(L-1)$$比如说还有这道题：2018.1.25区间子图(考试题)

代码

Luogu LCT模板

// luogu-judger-enable-o2

//注释详尽版本

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<set>

using namespace std;

int read()

{

    char ch=getchar();

    int h=0;

    while(ch>'9'||ch<'0')ch=getchar();

    while(ch>='0'&&ch<='9'){h=h*10+ch-'0';ch=getchar();}

    return h;

}

const int MAXN=300001;

set<int>Link[MAXN];

int N,M,val[MAXN],zhan[MAXN],top=0;

struct Splay{int val,sum,rev,ch[2],fa;}t[MAXN];

void Print()

{

    for(int i=1;i<=N;i++)

        printf("%d:val=%d,fa=%d,lc=%d,rc=%d,sum=%d,rev=%d\n",i,t[i].val,t[i].fa,t[i].ch[0],t[i].ch[1],t[i].sum,t[i].rev);

}

void pushup(int x)//向上维护异或和

{

    t[x].sum=t[t[x].ch[0]].sum^t[t[x].ch[1]].sum^t[x].val;//异或和

}

void reverse(int x)//打标记

{

    swap(t[x].ch[0],t[x].ch[1]);

    t[x].rev^=1;//标记表示已经翻转了该点的左右儿子

}

void pushdown(int x)//向下传递翻转标记

{

    if(!t[x].rev)return;

    if(t[x].ch[0])reverse(t[x].ch[0]);

    if(t[x].ch[1])reverse(t[x].ch[1]);

    t[x].rev=0;

}

bool isroot(int x)//如果x是所在链的根返回1

{

    return t[t[x].fa].ch[0]!=x&&t[t[x].fa].ch[1]!=x;

}

void rotate(int x)//Splay向上操作

{

    int y=t[x].fa,z=t[y].fa;

    int k=t[y].ch[1]==x;

    if(!isroot(y))t[z].ch[t[z].ch[1]==y]=x;//Attention if()

    t[x].fa=z;//注意了

    /*

      敲黑板：这个时候y为Splay的根，把x绕上去后

      x的父亲是z！表示这个splay所表示的原图中的链的链顶的父亲

      这正是splay根的父亲表示的是链顶的父亲的集中体现！

     */

    t[y].ch[k]=t[x].ch[k^1];t[t[x].ch[k^1]].fa=y;

    t[x].ch[k^1]=y;t[y].fa=x;

    pushup(y);

}

void splay(int x)//把x弄到根

{

    zhan[++top]=x;

    for(int pos=x;!isroot(pos);pos=t[pos].fa)zhan[++top]=t[pos].fa;

    while(top)pushdown(zhan[top--]);

    while(!isroot(x))

    {

        int y=t[x].fa,z=t[y].fa;

        if(!isroot(y))

            /*

              这个地方和普通Splay有所不同：

              普通的是z!=goal，z不是根的爸爸

              这个是y!=root，y不是根

              所以实质是一样的。。。

             */

            (t[y].ch[0]==x)^(t[z].ch[0]==y)?rotate(x):rotate(y);

        rotate(x);

    }

    pushup(x);

}

void Access(int x)

{

    for(int y=0;x;y=x,x=t[x].fa){splay(x);t[x].ch[1]=y;pushup(x);}

    /*

      Explaination:

      函数功能：把x到原图的同一个联通块的root弄成一条链，放在同一个Splay中

      首先令x原先所在splay的最左端(x所在链的链顶)为u

      那么x-u一定保留在x-root的路径中，那么直接断掉x的右儿子

      然后y是上一个这么处理的链的Splay所在的根

      在之前，y向x连了一条虚边(y的fa是x，x的ch不是y)

      那么只要化虚为实就可以了

     */

}

void makeroot(int x)//函数功能：把x拎成原图的根

{

    Access(x);splay(x);//把x和根先弄到一起

    reverse(x);//然后打区间翻转标记，应该在根的地方打但是找不到根所以要splay(x)

    /*

      这里很神奇的一个区间翻转标记，那么从上往下是root-x，翻转完区间就是x-root

      这样子相当于(这里打一个神奇的比喻)

      一根棒子上面有一些平铺的长毛，原先是向上拉，区间翻转后就向下拉

         |            ↑            |

     ----|----       /|\        \ \|/ /

     ----|----      / | \        \ | /

     ----|----     / /|\ \      \ \|/ /

     ----|----      / | \        \ | /

     ----|----     / /|\ \      \ \|/ /

     ----|----      / | \        \ | /

     ----|----     / /|\ \        \|/

         |            |            ↓

      哈哈哈夸我～

     */

}

int Findroot(int x)//函数功能：找到x所在联通块的splay的根

{

    Access(x);splay(x);

    while(t[x].ch[0])x=t[x].ch[0];

    return x;

}

void split(int x,int y)//函数功能：把x到y的路径抠出来

{

    makeroot(x);//先把x弄成原图的根

    Access(y);//再把y和根的路径弄成重链

    splay(y);//那么就是y及其左子树存储的信息了

    /*

      关于这里为什么要splay(y):

      可以发现，makeroot后x为splay的根

      但是Access之后改变了根(这就是为什么凡是Access都后面跟了splay)

      所以要找到根最方便就是splay，至于splayx还是y，都可以

     */

}

void link(int x,int y)//函数功能：连接x,y所在的两个联通块

{

    makeroot(x);//把x弄成其联通块的根

    t[x].fa=y;//连到y上（虚边）

    Link[x].insert(y);Link[y].insert(x);

}

void cut(int x,int y)//函数功能：割断x,y所在的两个联通块

{

    split(x,y);

    t[y].ch[0]=t[x].fa=0;

    Link[x].erase(y);Link[y].erase(x);

    /*

      这里会出现一个这样的情况：

      图中x和y并未直接连边，但是splay中有可能直接相连

      所以一定要用set(map会慢)维护实际的连边

      不然会出现莫名错误(大部分数据可以水过去，但是subtask...)

     */

}

int main()

{

    N=read();M=read();

    for(int i=1;i<=N;i++)

        t[i].sum=t[i].val=read();//原图中结点编号就是Splay结点编号

    for(int i=1;i<=M;i++)

    {

        int op=read(),x=read(),y=read();

        if(op==0)//x到y路径异或和

        {

            split(x,y);//抠出路径

            printf("%d\n",t[y].sum);

        }

        if(op==1)//连接x,y

        {

            if(Findroot(x)^Findroot(y))

                link(x,y);//x,y不在同一联通块里

        }

        if(op==2)//割断x,y

        {

            if(Link[x].find(y)!=Link[x].end())

                cut(x,y);//x,y在同一联通块

        }

        if(op==3)//把x点的权值改成y

        {

            Access(x);//把x到根的路径设置为重链

            splay(x);//把x弄到该链的根结点

            t[x].val=y;

            pushup(x);//直接改x的val并更新

        }

        //printf("i=%d\n",i);

        //Print();

    }

    return 0;

}

秒客网

Link Cut Tree 总结

Link-Cut-Tree

更好阅读体验：https://www.zybuluo.com/xzyxzy/note/1027479

一、概述

二、题目

初步

进阶

变态

三、支持操作

例题：“初步”中水管局长到温暖会指引我们前行

引入：一条路径的权值定义为该路径上所有边的边权最大值，问x到y的所有路径中，路径权值最小的路径的权值是多少，要求支持加边或删边，\(O(nlogn)\)求解

解决：

pushup片段

例题：星球联盟、长跑

解释：

实现：

核心代码片段

例题：大融合、动态树

解释：

实现

核心代码片段

四、做题经验

1、辨别

2、常数

3、所谓奇技淫巧

代码

相关文章