CF1827D Two Centroids 题解

· · 题解

Solution

先不考虑修改，只给定一棵树，求使其拥有两个重心最少加几个叶子能满足？个人认为答案很容易得出：如果现在只有一个重心，那么往以其为根得到的子树大小最大的儿子节点一直挂叶子肯定最优，设那个点的子树大小为 m，最少挂 n-2m 个点，使得两部分皆为 \dfrac{n+(n-2m)}{2}=n-m 个点。

现在这棵树在“动态”加点（并没有强制在线），对重心会有何影响呢？假设原重心在 x，由于每次只加了 1 个点，最坏情况下会使 x 进行距离为 1 的位移，因为只有加入的那个点刚好使得重心对应出边那一坨子树大小达到临界值迫使重心异位。

其实这个题分析到这里基本结束了。

输入后先把最终树的形态确定下来。维护当前重心所在位置，加点时若在重心子树内，判断当前点祖先且是重心儿子的那个点现在子树大小是否超过临界，超过了重心会下跳，否则重心不会变；要不然不在重心子树内，是类似的判断，超过了重心就上跳。过程中顺便维护重心所有儿子的子树大小最大值。

在动态加点过程中查询子树大小可用 dfs 序与树状数组维护。

Code

#include<bits/stdc++.h>
inline int lowbit(int x){
    return x&-x; 
}
std::vector<int>v[500005];
int fa[500005][20];
int dep[500005];
int L[500005],R[500005],tdx;
void dfs(int p){
    L[p]=++tdx;
    dep[p]=dep[fa[p][0]]+1;
    for(int i=1;i<20;++i)
        fa[p][i]=fa[fa[p][i-1]][i-1];
    for(const int&i:v[p])
        fa[i][0]=p,dfs(i);
    R[p]=tdx;
}
inline int up(int x,int y){
    for(int i=19;~i;--i)
        if(dep[fa[x][i]]>dep[y])x=fa[x][i];
    return x;
}
int bit[500005];
int n;
inline void add(int x){
    for(;x<=n;x+=lowbit(x))++bit[x];
}
inline int ask(int x){
    static int res;res=0;
    for(;x;x^=lowbit(x))res+=bit[x];
    return res;
}
int T,rt,w;
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        for(int i=1;i<=n;++i)v[i].clear();
        for(int i=2,x;i<=n;++i)
            scanf("%d",&x),v[x].push_back(i);
        tdx=0;dfs(rt=1);
        memset(bit+1,w=0,n<<2);
        for(int i=2,j,k;i<=n;++i){
            add(L[i]);
            if(L[rt]<=L[i]&&L[i]<=R[rt]){
                j=up(i,rt);k=ask(R[j])-ask(L[j]-1);
                if(k>(i>>1))rt=j,w=i>>1;
                else w=std::max(w,k);
            }else{
                k=i-ask(R[rt])+ask(L[rt]-1);
                if(k>(i>>1))rt=fa[rt][0],w=i>>1;
                else w=std::max(w,k);
            }
            printf("%d ",i-(w<<1));
        }
        putchar(10);
    }
    return 0;
}