Luogu4299 首都

Description

有 $n$ 个点，初始时互不连通。有 $q$ 次操作，分别为如下三种类型：

• 连接 $x\ y$ 两个点。保证 $x\ y$ 不连通。
• 询问编号为 $x$ 的点所在的树的重心的编号。
• 询问当前所有树的重心的编号异或和。

重心定义为某个使得其他点到它的距离之和最小的点。有多个重心时选择编号最小的。
$n\leq 10^5,m\leq 2\times 10^5$

Solution

重心的性质很优美，大致来说有四个：

• 树中所有点到某个点的距离和中，到重心的距离和是最小的。
• 以树的重心为根时，除根节点以外所有节点的子树大小均不超过 $\frac{n}{2}$ 。
• 把两棵树通过某一点相连得到一颗新的树，新的树的重心必然在连接原来两棵树重心的路径上。
• 当在原树上新增/删除一个叶子节点时，重心至多移动一条边的距离。

对于这道题而言，第二条和第三条实在是再好不过了。
这里简要证明以下第三条性质。不在路径上的点在原树上的子树大小不超过原树大小的一半，那么当删去它的子树后不小于原树大小的一半。而删去它的子树后的这个连通块完整继承了另一棵树的所有节点，故连通块的大小一定大于新树大小的一半。
有了上述性质，我们就将重心的范围限制在了一条链上。
链上的点除了向两个重心方向的子树外，其余的子树的大小一定小于新树大小的一半。我们只需考虑链上的点向两个重心方向的子树。用 splay 维护这条链，每个节点额外代表链上的一个区间，到达节点时比较 左/右子节点的大小与区间左端点以左（lsum）/右端点以右的大小（rsum）之和（也就是该节点向着两个重心的子树大小） 与新树大小的一半的大小。如果均为不大于，那么该节点自然就是重心啦；否则更新 lsum/rsum ，再进入子树大小较大的那一边继续找。
可能讲得有些复杂了，实际上只要看懂了还是很好理解的。类似于树上二分嘛。

问题转化为要求取出树上一条链，并且用 splay 维护它。当然是 LCT 啦。

复杂度 $\mathcal{O}(m\log_2{n})$ 。

Code

const int N=1e5+6;
using namespace std;
namespace LCT{
#define lc(x) c[x][0]
#define rc(x) c[x][1]
    int sz[N],fa[N],vir[N],tag[N],c[N][2]; 
    inline bool nrt(int x){return lc(fa[x])==x || rc(fa[x])==x;}
    inline void update(int x){
        sz[x]=sz[lc(x)]+sz[rc(x)]+vir[x]+1;
    }
    inline void revers(int x){
        tag[x]^=1;swap(lc(x),rc(x));
    }
    inline void pushdn(int x){
        revers(lc(x)),revers(rc(x)),tag[x]=0;
    }
    inline void rotate(int x){
        int y=fa[x],z=fa[y],t=rc(y)==x;
        if(nrt(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 pushall(int x){
        if(nrt(x)) pushall(fa[x]);
        if(tag[x]) pushdn(x);
    }
    inline void splay(int x){
        pushall(x);
        while(nrt(x)){
            int y=fa[x],z=fa[y];
            if(nrt(y))
                ((rc(y)==x)^(rc(z)==y))?rotate(x):rotate(y);
            rotate(x);
        }
    }
    inline 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);
    }
    inline void makert(int x){
        access(x);splay(x);revers(x);
    }
    inline void split(int x,int y){
        makert(x);access(y);splay(y);
    }
    inline void link(int x,int y){
        split(x,y);fa[x]=y;vir[y]+=sz[x];update(y);
    }
    int solve(int x){
        int Max=sz[x]>>1,Jud=sz[x]&1,lsum=0,rsum=0,ret=0x3f3f3f3f;
        while(x){
            if(tag[x]) pushdn(x);
            int nowl=lsum+sz[lc(x)],nowr=rsum+sz[rc(x)];
            if(nowl<=Max&&nowr<=Max)
                if(Jud){ret=x;break;}
                else if(ret>x) ret=x;
            if(nowl<nowr) lsum+=sz[x]-sz[rc(x)],x=rc(x);
            else rsum+=sz[x]-sz[lc(x)],x=lc(x);
        }
        return ret;
    }
}
using namespace LCT;
int n,m,f[N];
int Find(int x){return f[x]==x?x:f[x]=Find(f[x]);}
int main(){

    scanf("%d%d",&n,&m);
    int ans=0;
    for(int i=1;i<=n;++i) sz[i]=1,f[i]=i,ans^=i;
    char s[10];
    for(int i=1,x,y;i<=m;++i){
        scanf("%s",s);
        if(s[0]=='X') w(ans),putchar(10);
        else if(s[0]=='Q') scanf("%d",&x),w(Find(x)),putchar(10);
        else{
            scanf("%d%d",&x,&y);link(x,y);
            split(x=Find(x),y=Find(y));
            int now=solve(y);
            f[x]=f[y]=f[now]=now;
            ans^=x^y^now;
        }
    }
    return 0;
}