【LCT维护子树信息】uoj207 共价大爷游长沙

这道题思路方面就不多讲了，主要是通过这题学一下lct维护子树信息。

lct某节点u的子树信息由其重链的一棵splay上信息和若干轻儿子子树信息合并而成。

splay是有子树结构的，可以在rotate，access的时候由儿子update到父亲，而轻儿子的信息update不上来，需要另外记一下。

记sum[x]为我们要求的子树信息，xu[x]为x的轻儿子的子树信息。

（即，xu[x]由轻儿子的sum更新，sum[x]由xu[x]和splay子树上的儿子的sum更新。

这样我们就可以完整地用lct维护子树信息了。

需要注意的是，修改点权的时候一定要先make_root，不然会影响到祖先的sum和xu，复杂度就不对了。

#include<bits/stdc++.h>

using namespace std;

#define rep(i,a,b) for(int i=(a);i<=(b);++i)

int n,m,id;

const int N =200005;

typedef unsigned long long ll;

inline int read(){

    int x=0,f=1;char ch=getchar();

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

    while(ch<='9'&&ch>='0')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();

    return x;

}

struct la{int u,v;ll x;}w[3*N];

ll S;

int cnt;

#define ju(x) (ch[fa[x]][1]==x)

#define nrt(x) ((ch[fa[x]][1]==x)||(ch[fa[x]][0]==x))

int fa[N],ch[N][2];

ll val[N],sum[N],xu[N];

bool r[N];

#define lc (ch[x][0])

#define rc (ch[x][1])

void ud(int x){

    sum[x]=sum[lc]^sum[rc]^val[x]^xu[x];

}

inline void rev(int x){swap(lc,rc),r[x]^=1;}

void psdn(int x){

    if(r[x]){

        if(lc)rev(lc);

        if(rc)rev(rc);

        r[x]=0;

    }

}

void push(int x){

    if(nrt(x))push(fa[x]);

    psdn(x);

}

inline void rot(int x){

    int f=fa[x],of=fa[f],dir=ju(x),nt=nrt(f);

    if(ch[x][dir^1])fa[ch[x][dir^1]]=f;

    ch[f][dir]=ch[x][dir^1];

    fa[f]=x,ch[x][dir^1]=f;

    fa[x]=of;

    if(nt)ch[of][ch[of][1]==f]=x;

    ud(f),ud(x);

}

inline void splay(int x){

    push(x);

    for(int f=fa[x];nrt(x);rot(x),f=fa[x])

    if(nrt(f))if(ju(x)^ju(f))rot(x);else rot(f);

}

inline void access(int x){

    for(int y=0;x;x=fa[y=x]){

        splay(x);

        xu[x]^=sum[y];

        xu[x]^=sum[ch[x][1]];

        ch[x][1]=y;

        ud(x);

        //update!

    }

}

inline void make_root(int x){

    access(x),splay(x),rev(x);

}

inline void cut(int x,int y){

    make_root(x),access(y),splay(x);

    ch[x][1]=fa[y]=0;ud(x);

}

inline void link(int x,int y){

    make_root(y),splay(y),make_root(x),splay(x),fa[x]=y;xu[y]^=sum[x];

}

inline void change(int x,ll v){

    make_root(x);splay(x);val[x]^=v;

    ud(x);

}

int main(){

    srand(time(0));

    id=read(),n=read(),m=read();

    int u,v,op,x,y;

    rep(i,2,n)scanf("%d%d",&u,&v),link(u,v);

    while(m--){

        op=read(),u=read();

        if(op==1){

            v=read(),x=read(),y=read();

            cut(u,v),link(x,y);

        }

        else if(op==2){

            v=read();

            w[++cnt]=(la){u,v,(ll)1ll*rand()*rand()};

            change(u,w[cnt].x),change(v,w[cnt].x);

            S^=w[cnt].x;

        }

        else if(op==3){

            x=w[u].u,y=w[u].v;

            change(x,w[u].x),change(y,w[u].x);

            S^=w[u].x;

        }

        else{

            v=read();

            make_root(u),access(v);

            splay(u);

            if(S==sum[v])puts("YES");

            else puts("NO");

        }

    }

    return 0;

}

巴特西

【LCT维护子树信息】uoj207 共价大爷游长沙

最新文章

热门文章