Loading...

洛谷P3690 [模板]Link Cut Tree (动态树)

check评论:0 条 remove_red_eye浏览量:443 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2018-10-22

蒟蒻终于会$LCT$啦qwq

首先最重要的操作$access$,是打通当前节点到$root$,保证当前节点在重链上,即在同一棵$splay$里面,我们每次将结点$splay$,然后网上翻救星

$makeroot$也很简单,$access$后直接$splay$它就变成根了

$findroot$同理,我们到根后一直往左儿子走就可以了,保证根只有右儿子

就可以轻易得到$split$操作,即拉出$x-y$的路径,代码如下

void split(int x,int y)
{
    makeroot(x);
    access(y);
    splay(y);
}

$link$,$cut$以及其他的操作自然就很简单了

#include <bits/stdc++.h>
using namespace std;
#define maxn 300010
namespace LCT
{
    int ch[maxn][2],f[maxn],siz[maxn],key[maxn],sum[maxn];
    bool rev[maxn];
    void update(int x)
    {
        siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+1;
        sum[x]=sum[ch[x][0]]^sum[ch[x][1]]^key[x];
    }
    bool isroot(int x)
    {
        return ch[f[x]][0]!=x&&ch[f[x]][1]!=x;
    }
    int get(int x)
    {
        return ch[f[x]][1]==x;
    }
    void pushdown(int x)
    {
        if(rev[x])
        {
            rev[x]=0;
            rev[ch[x][0]]^=1;
            rev[ch[x][1]]^=1;
            swap(ch[x][0],ch[x][1]);
        }
    }
    void rotate(int x)
    {
        int old=f[x],oldf=f[old],which=get(x);
        if(!isroot(old))
        {
            ch[oldf][get(old)]=x;
        }
        ch[old][which]=ch[x][!which];
        f[ch[x][!which]]=old;
        ch[x][!which]=old;
        f[old]=x;
        f[x]=oldf;
        update(old);
        update(x);
    }
    void splay(int x)
    {
        stack<int> st;
        st.push(x);
        for(int i=x;!isroot(i);i=f[i])
        {
            st.push(f[i]);
        }
        while(!st.empty())
        {
            pushdown(st.top());
            st.pop();
        }
        for(int fa=f[x];!isroot(x);rotate(x),fa=f[x])
        {
            if(!isroot(fa))
            {
                rotate(get(x)==get(fa)?fa:x);
            }
        }
        update(x);
    }
    void access(int x)
    {
        for(int y=0;x;x=f[y=x])
        {
            splay(x);
            ch[x][1]=y;
            update(x);
        }
    }
    int findroot(int x)
    {
        access(x);
        splay(x);
        while(ch[x][0])
        {
            pushdown(x);
            x=ch[x][0];
        }
        return x;
    }
    void makeroot(int x)
    {
        access(x);
        splay(x);
        rev[x]^=1;
    }
    void link(int x,int y)
    {
        makeroot(x);
        f[x]=y;    
    }
    void cut(int x,int y)
    {
        makeroot(x);
        access(y);
        splay(y);
        if(ch[y][get(x)^1]||f[x]!=y||ch[x][1])
        {
            return ;
        }
        f[x]=ch[y][0]=0;
        update(y);
    }
    int query(int x,int y)
    {
        makeroot(x);
        if(findroot(y)==x)
        {
            return true;
        }
    }
}
using namespace LCT;
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&key[i]);
        sum[i]=key[i];
    }
    for(int i=1;i<=m;i++)
    {
        int opt,x,y;
        scanf("%d%d%d",&opt,&x,&y);
        if(opt==0)
        {
            makeroot(x);
            access(y);
            splay(y);
            printf("%d\n",sum[y]);
        }
        if(opt==1&&findroot(x)!=findroot(y))
        {
            link(x,y);
        }
        if(opt==2&&findroot(x)==findroot(y))
        {
            cut(x,y);
        }
        if(opt==3)
        {
            key[x]=y;
            access(x);
            splay(x);
            update(x);
        }
    }
}

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名