Query on a tree VI

Description

给你一棵 $n$ 个点的树，每个点为黑色或白色。要求维护两个操作：

• 改变点 u 的颜色
• 查询包含点 u 的同色连通块大小

$n,q\leq 10^5$

Solution

动态维护连通块可以考虑 LCT 。但是当一个点颜色改变时如果我们枚举其所有出边来更改，复杂度爆炸。

平常都是把边的信息放在点上，因为边数比点数少，信息一定不会有缺失；很少把点的信息放在边上。
实际上，点的信息也是可以放在边上的。对于非根节点，每个点的信息放在父边上；对于根节点，我们另开一个虚拟根节点与其连边用来存根节点的信息。

具体于本题而言，我们建两棵 LCT ，分别代表黑/白色。在 LCT 中，我们只加入对应颜色的边。点 u 在颜色 c[u] 对应的 LCT 上的最远祖先一定是虚拟节点/异色节点，即 findroot(u) 后，根的重子树大小就是包含点 u 的同色连通块大小（因为 findroot 中 splay 了根节点）。根的重儿子必定是其右儿子。

问题转化为维护 LCT 上 u 的子树大小，维护一个 vir[u] 表示连向 u 的所有轻链 size 即可。

需要注意的是，在本题中，树的形态是固定的，也就是我们不能进行 makeroot 操作。但庆幸的是，经过上述分析后，我们可以发现 link 和 cut 操作都是恰好针对点 u 和其父节点来的，故仍然可以实现。

Code

struct LCT{
#define lc(x) c[x][0]
#define rc(x) c[x][1]
    int sz[N],fa[N],vir[N],c[N][2];
    LCT(){for(int i=1;i<N;++i) sz[i]=1;}
    inline void update(int x){
        sz[x]=sz[lc(x)]+sz[rc(x)]+vir[x]+1;
    }
    inline bool isrt(int x){
        return fa[x]==0 || (lc(fa[x])!=x&&rc(fa[x])!=x);
    }
    inline void rotate(int x){
        int y=fa[x],z=fa[y],t=rc(y)==x;
        if(!isrt(y)) c[z][rc(z)==y]=x;fa[x]=z;
        c[y][t]=c[x][t^1];fa[c[x][t^1]]=y;
        c[x][t^1]=y;fa[y]=x;
        update(y),update(x);
    }
    void splay(int x){
        while(!isrt(x)){
            int y=fa[x],z=fa[y];
            if(!isrt(y))
                ((rc(y)==x)^(rc(z)==y))?rotate(x):rotate(y);
            rotate(x);
        }
    }
    void access(int x){
        for(int i=0;x;x=fa[i=x])
            splay(x),vir[x]+=sz[rc(x)],rc(x)=i,vir[x]-=sz[i],update(x);
    }
    int findrt(int x){                          
        access(x);splay(x);
        while(lc(x)) 
            x=lc(x);
        splay(x);
        return x;
    }
    void link(int x,int y){
        splay(x);fa[x]=y;
        access(y),splay(y);
        vir[y]+=sz[x];sz[y]+=sz[x];
    }
    void cut(int x,int y){
        access(x),splay(x),lc(x)=fa[lc(x)]=0;update(x);
    }
}t[2];