【SPOJ16549】QTREE6 - Query on a tree VI | Mrsrz's blog

LCT。

题目大意：

给定一棵树，每个结点为黑色或白色，初始为同一种颜色。有两个操作：

1. 给定 $u$，询问 $u$ 所在的同色连通块的大小。
2. 给定 $u$，翻转 $u$ 的颜色。

题解：

比较容易想到的是对两种颜色分别用 LCT 维护树的结构，存储子树大小之类的。但修改一次颜色会造成 $O(n)$ 条边的变动（比如一张菊花图），复杂度不正确。

一个挺妙的 Trick。

我们考虑修改一个点的颜色的时候，只修改这个点连向父亲的边。

然后考虑一次询问，这个点所在的连通块可能有两种情况：颜色全部相同；只有根结点颜色不同。

对于第一种情况很好处理。对于第二种情况，我们只需要 access 完后，找到根所在的 splay 的右儿子的值即可。

这样每次只会修改 $O(1)$ 条边，复杂度正确。

由于这里树的形态不能改变（否则找不到正确的根，就无法判断不同色的那个点了），所以我们不能使用 makeroot 操作。而又因为树的形态不变，每个点的父亲不变，因此可以避免 makeroot 操作完成 link 和 cut 操作，这样每个结点 findroot 的时候找到的根就是正确的了。

具体细节可参考代码的 LCT 部分。

时间复杂度 $O((n+m)\log n)$。

Code：

#include<iostream>
#include<algorithm>
using namespace std;
const int N=3e5+6;
int n,m,head[N],cnt,fa[N],dep[N];
bool col[N];
struct lct{
    int ch[N][2],fa[N],val[N],sz[N],sm[N],_v[N];
    bool tag[N];
    inline bool ckr(int x,int p=1){return ch[fa[x]][p]==x;}
    inline bool isroot(int x){return!(ckr(x)||ckr(x,0));}
    inline void update(int x){
        sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+1;
        sm[x]=sm[ch[x][0]]+sm[ch[x][1]]+_v[x]+val[x];
    }
    inline void flip(int x){swap(ch[x][0],ch[x][1]),tag[x]^=1;}
    inline void pushdown(int x){
        if(tag[x]){
            if(ch[x][0])flip(ch[x][0]);
            if(ch[x][1])flip(ch[x][1]);
            tag[x]=0;
        }
    }
    void rotate(int x){
        int y=fa[x],z=fa[y],k=ckr(x);
        if(!isroot(y))ch[z][ckr(y)]=x;
        fa[x]=z,fa[y]=x,fa[ch[x][!k]]=y;
        ch[y][k]=ch[x][!k],ch[x][!k]=y;update(y);
    }
    void splay(int x){
        static int sta[N],top;sta[top=1]=x;
        for(int y=x;!isroot(y);sta[++top]=y=fa[y]);
        while(top)pushdown(sta[top--]);
        for(;!isroot(x);rotate(x))
        if(!isroot(fa[x]))rotate((ckr(x)^ckr(fa[x]))?x:fa[x]);
        update(x);
    }
    void access(int x){
        for(int t=0;x;_v[x]-=sm[t]-sm[ch[x][1]],ch[x][1]=t,t=x,x=fa[x])splay(x);
    }
    void makeroot(int x){access(x),splay(x),flip(x);}
    void link(int x,int y){splay(x),access(y),splay(y),fa[x]=y,_v[y]+=sm[x],update(y);}
    void cut(int x,int y){access(x),splay(y),ch[y][1]=fa[x]=0,update(y);}
    int findroot(int x){access(x);for(splay(x);ch[x][0];x=ch[x][0]);splay(x);return x;}
    void init(){
        for(int i=1;i<=n;++i)sz[i]=sz[i+n]=val[i]=sm[i]=1;
    }
    int ask(int u,bool cl){
        int x=findroot(u);
        if(col[x]==cl)return sm[x];
        return sm[ch[x][1]];
    }
}T[2];
struct edge{
    int to,nxt;
}e[N<<1];
void dfs(int now){
    for(int i=head[now];i;i=e[i].nxt)
    if(!dep[e[i].to]){
        dep[e[i].to]=dep[now]+1,fa[e[i].to]=now;
        dfs(e[i].to);
    }
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<n;++i){
        int u,v;
        cin>>u>>v;
        e[++cnt]=(edge){v,head[u]},head[u]=cnt;
        e[++cnt]=(edge){u,head[v]},head[v]=cnt;
    }
    dfs(dep[1]=1);
    T[0].init(),T[1].init();
    for(int i=2;i<=n;++i){
        T[0].link(i,i+n);
        T[0].link(i+n,fa[i]);
    }
    for(cin>>m;m--;){
        int op,u;
        cin>>op>>u;
        if(op){
            bool&c=col[u];
            if(u==1){
                c=!c;
                continue;
            }
            T[c].cut(u,u+n);
            T[c].cut(u+n,fa[u]);
            T[c=!c].link(u,u+n);
            T[c].link(u+n,fa[u]);
        }else cout<<T[col[u]].ask(u,col[u])<<'\n';
    }
    return 0;
}