BZOJ 3637: Query on a tree VI LCT_维护子树信息_点权转边权_好题

非常喜欢这道题。

点权转边权，这样每次在切断一个点的所有儿子的时候只断掉一条边即可。

Code:

#include <cstring>

#include <cstdio>

#include <algorithm>

#include <string>

#define setIO(s) freopen(s".in","r",stdin);

#define maxn 100009

using namespace std;

int fat[maxn];

int n,m;

struct Graph{

    int head[maxn],to[maxn<<1],nex[maxn<<1],cnt;

    void addedge(int u,int v){ nex[++cnt]=head[u],head[u]=cnt,to[cnt]=v; }

    void dfs(int u,int father){

        fat[u]=father;

        for(int v=head[u];v;v=nex[v]) if(to[v]!=father) dfs(to[v],u);

    }

    void Build(){

        for(int i=1;i<n;++i){

            int a,b;

            scanf("%d%d",&a,&b), addedge(a,b),addedge(b,a);

        }

        dfs(1,0);

    }

}G;

int col[maxn];

struct LCT{

    int ch[maxn][2],f[maxn];

    int siz[maxn],son[maxn];

    int get(int x){ return ch[f[x]][1]==x; }

    int lson(int x){ return ch[x][0];}

    int rson(int x){ return ch[x][1];}

    int isRoot(int x){ return !(ch[f[x]][0]==x||ch[f[x]][1]==x); }

    void pushup(int x){ siz[x]=siz[lson(x)]+siz[rson(x)]+son[x]+1; }

    void rotate(int x)

    {

        int old=f[x],oldf=f[old],which=get(x);

        if(!isRoot(old)) ch[oldf][ch[oldf][1]==old]=x;

        ch[old][which]=ch[x][which^1],f[ch[old][which]]=old;

        ch[x][which^1]=old,f[old]=x,f[x]=oldf;

        pushup(old),pushup(x);

    }

    void splay(int x)

    {

        int u=x;

        while(!isRoot(u)) u=f[u];

        u=f[u];

        for(int fa;(fa=f[x])!=u;rotate(x))

            if(f[fa]!=u) rotate(get(fa)==get(x)?fa:x);

    }

    void Access(int x){

        for(int y=0;x;y=x,x=f[x])

            splay(x),son[x]=son[x]+siz[ch[x][1]]-siz[y],ch[x][1]=y,pushup(x);

    }

    void cut(int a,int b){

        if(!a) return;

        Access(b),splay(b),ch[b][0]=f[ch[b][0]]=0,pushup(b);

    }

    void link(int a,int b)

    {

        if(!a) return;

        Access(a),splay(a),Access(b),splay(b);

        f[b]=a,ch[a][1]=b,pushup(a);

    }

    int findRoot(int a){

        Access(a),splay(a);

        while(ch[a][0]) a=ch[a][0];

        return a;

    }

}tree[2];

int main(){

    //setIO("input");

    scanf("%d",&n),G.Build();

    for(int i=2;i<=n;++i) tree[0].link(fat[i],i);

    int opt,a;

    scanf("%d",&m);

    for(int i=1;i<=m;++i){

        scanf("%d%d",&opt,&a);

        if(opt==1) {

            tree[col[a]].cut(fat[a],a),col[a]^=1,tree[col[a]].link(fat[a],a);

        }

        if(opt==0) {

            int x=tree[col[a]].findRoot(a);

            tree[col[a]].splay(x);

            if(col[x]==col[a]) printf("%d\n",tree[col[a]].siz[x]);

            else printf("%d\n",tree[col[a]].siz[tree[col[a]].ch[x][1]]);

        }

    }

    return 0;

}