zcmimi's blog
查看原题

点击跳转

LCT维护重心

这里利用了两个重心性质:

  1. 树中所有点到某个点的距离和中,到重心的距离和是最小的,如果有两个距离和,他们的距离和一样。

  2. 把两棵树通过某一点相连得到一颗新的树,新的树的重心必然在连接原来两棵树重心的路径上。

我们需要维护子树的大小

合并的时候连接两棵树,分离出连接原来两棵树重心的路径,在链上搜索出答案

方法类似平衡树的查找

#include<bits/stdc++.h>
const int N=100011;
int n,q,s[N],s2[N],c[2][N],f[N],bl[N],ans;
bool rev[N];
int BL(int x){return x==bl[x]?x:(bl[x]=BL(bl[x]));}
#define ls c[0][x]
#define rs c[1][x]
void pu(int x){s[x]=s[ls]+s[rs]+1+s2[x];}
void pr(int x){rev[x]^=1;ls^=rs,rs^=ls,ls^=rs;}
void pd(int x){
    if(rev[x]){
        if(ls)pr(ls);
        if(rs)pr(rs);
        rev[x]=0;
    }
}
int g(int x){return c[1][f[x]]==x;}
int nrt(int x){return c[0][f[x]]==x||c[1][f[x]]==x;}
void rotate(int x){
    int y=f[x],z=f[y],l=g(x),r=!l,w=c[r][x];
    if(nrt(y))c[g(y)][z]=x;
    c[r][x]=y,c[l][y]=w;
    if(w)f[w]=y;
    f[x]=z,f[y]=x;
    pu(y),pu(x);
}
void pda(int x){if(nrt(x))pda(f[x]);pd(x);}
void splay(int x){
    for(pda(x);nrt(x);rotate(x))if(nrt(f[x]))
        rotate(g(x)^g(f[x])?x:f[x]);
    pu(x);
}
void access(int x){
    for(int y=0;x;x=f[y=x])
        splay(x),s2[x]+=s[rs]-s[rs=y],pu(x);
}
void mrt(int x){access(x),splay(x),pr(x);}
void link(int x,int y){
    mrt(x),access(y),splay(y);
    f[x]=y;
    s2[y]+=s[x];
    pu(y);
}
int find(int x){
    bool ff=s[x]&1;
    int sum=s[x]>>1,cl,cr,as=n+1,lsum=0,rsum=0;
    while(x){
        pd(x);
        cl=s[ls]+lsum,cr=s[rs]+rsum;
        if(cl<=sum&&cr<=sum){
            if(ff)return x;
            else if(as>x)as=x;
        }
        if(cl<cr)lsum+=s[ls]+s2[x]+1,x=rs;
        else rsum+=s[rs]+s2[x]+1,x=ls;
    }
    return as;
}
int main(){
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;++i)s[i]=1,bl[i]=i,ans^=i;
    char opt[5];
    int x,y;
    while(q--){
        scanf("%s",opt);
        if(opt[0]=='X')printf("%d\n",ans);
        else if(opt[0]=='Q')
            scanf("%d",&x),
            printf("%d\n",BL(x));
        else{
            scanf("%d%d",&x,&y);
            link(x,y);
            x=BL(x),y=BL(y);
            mrt(x),access(y),splay(y);
            int z=find(y);
            bl[x]=bl[y]=bl[z]=z;
            ans^=x^y^z;
            splay(z);
        }
    }
}
LG 4299 首都
comment评论
Search
search