@MLEAutoMaton 2019-04-18T00:11:13.000000Z 字数 1973 阅读 737

Link-Cut-Tree总结

学习笔记

模板篇

LCT在笔者目前的学习中好像只用到了模板...~~菜死了~~
如果现在需要支持动态加边/删边然后询问链怎么做?
如果不动态的话树链剖分就好了,那么我们考虑用Splay维护实链剖分.
Splay的左儿子是实链,右儿子是虚链,Splay的过程不变.
~~不小心压行了,将就看吧.~~

void pushup(int x)
{
    //pushup比较灵活,看你要维护什么东西,就怎么写.
}
void reverse(int x)
{
    t[x].rev^=1;
    swap(t[x].ch[0],t[x].ch[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^=1;
}
bool isroot(int x)
{
    return (t[t[x].ff].ch[0]!=x)&(t[t[x].ff].ch[1]!=x);
}
void rotate(int x)
{
    int y=t[x].ff,z=t[y].ff;
    if(!isroot(y))t[z].ch[t[z].ch[1]==y]=x;
    t[x].ff=z;int k=t[y].ch[1]==x;
    t[y].ch[k]=t[x].ch[k^1];
    t[t[x].ch[k^1]].ff=y;
    t[x].ch[k^1]=y;t[y].ff=x;
}
void splay(int x)
{
    sta[++top]=x;for(int pos=x;!isroot(pos);pos=t[pos].ff)sta[++top]=t[pos].ff;while(top)pushdown(sta[top--]);
    while(!isroot(x)){int y=t[x].ff,z=t[y].ff;if(!isroot(y))(t[y].ch[1]==x)^(t[z].ch[1]==y)?rotate(x):rotate(y);rotate(x);}
}

剩下的操作基本就是套路,~~不需要理解吧~~.

void access(int x){for(int y=0;x;y=x,x=t[x].ff)splay(x),t[x].ch[1]=y;}
void makeroot(int x){access(x);splay(x);reverse(x);}
int findroot(int x){access(x);splay(x);while(t[x].ch[0])x=t[x].ch[0];return x;}
void split(int x,int y){makeroot(x);access(y);splay(y);}
void link(int x,int y){makeroot(x);t[x].ff=y;}
void cut(int x,int y){split(x,y);t[x].ff=t[y].ch[0]=0;}

应用篇

入门

中级

进阶

维护动态图连通性

入门的[SDOI2008]洞穴勘测.
这个不需要维护别的,只要维修连通性,所以不需要pushup,对应的就是上面的模板代码.

维护链(路径)的信息

入门的【模板】Link Cut Tree（动态树）
中级的[国家集训队]Tree II
就只要pushup的时候写一点东西就好了.

维护最小/大生成树

emmm,比较难理解~~想了2个晚自习...~~
对应的题目大概是入门的[Wc2006]水管局长(其实也不是很入门)和中级的最小差值生成树.
如果已经维护了一个最小生成树,那么如果再加入一条边,那么就会构成一个环...
考虑维护的生成树,如果是最大,就要把环上的最小边去掉,反之.
然后就可以把边看成点,正常维护就好了.
注意考虑自环的影响.

维护子树信息

emmm,原树中的子树不就是虚子树+实子树?
然后直接对于每一个点维护一下虚的信息就好了.
大致改一下pushup和access:

void pushup(int x){t[x].siz=t[t[x].ch[0]].siz+t[t[x].ch[1]].siz+1+t[x].si;}
void access(int x)
{
    for(int y=0;x;y=x,x=t[x].ff)
    {
        splay(x);
        t[x].si+=t[t[x].ch[1]].siz;
        t[x].si-=t[t[x].ch[1]=y].siz;
        pushup(x);
    }
}