题解 CF708C 【Centroids】

CF708C Centroids

对于一个非重心的节点 u，我们肯定需要从这个大小大于 \frac{n}{2} 的连通块中拿掉一个子树并移到别的节点上区。显然，我们肯定是移到 u 上。

所以，我们选出的这个子树大小不能大于 \frac{n}{2} 。也就是说，我们需要算出从那个连通块中，能选出大小不超过 \frac{n}{2} 的最大子树，然后如果把这个最大子树移掉后连通块大小小于 \frac{n}{2}，那么这个点就可以通过一次删边加边操作成为重心。

一个节点被拿掉后的连通块可以分为两种：自己孩子的子树和其他部分。所以我们可以用二次扫描去做换根 dp。

我们记录 f_{u,0} 为子树最多能移出多少个点。由于要换根 dp，所以我们还要记录第二多可以移出多少个点（f_{u,1}）和第一大的决策（即儿子的编号）mx_u。

对于求子树中的 f_u，我们遍历每个儿子，如果这个儿子子树大小不大于 \frac{n}{2}，那么代表可以直接把这个儿子移掉。如果大于，那么就只能移掉 f_{son}。

int f[N][2],mx[N]; 
void dfs1(int u,int fa){ //计算f[u][0/1]和mx[u] 
    for(int i=hd[u],v;i;i=e[i].nxt)
        if((v=e[i].to)!=fa){
            dfs1(v,u);
            int tmp=(sz[v]>n/2?f[v][0]:sz[v]);
            if(tmp>f[u][0]) f[u][1]=f[u][0],f[u][0]=tmp,mx[u]=v;
            else if(tmp>f[u][1]) f[u][1]=tmp;
        }
}

我们记录 g_u 为子树外部最大值。

对于求子树外的 g_v，对于父亲节点 u 的子节点 v。如果 v 子树外部的节点个数不大于 \frac{n}{2}，我们可以直接把外部的移掉。否则，我们有几种方法。 第一，移掉 g_u。第二，移掉自己的兄弟子树。

int g[N];
void dfs2(int u,int fa){ //计算 g[u] 
    for(int i=hd[u],v;i;i=e[i].nxt)
        if((v=e[i].to)!=fa){
            int tmp=(n-sz[v]>n/2?g[u]:n-sz[v]);
            g[v]=max(g[v],tmp);
            if(v==mx[u]) g[v]=max(g[v],f[u][1]);
            else g[v]=max(g[v],f[u][0]);
            dfs2(v,u);
        }
}

最后计算答案的时候还要记录一下自己为根时的有最大子树大小的儿子节点 msz_u。

总体代码：

#include<bits/stdc++.h>
using namespace std;
const int N=4e5+9;
struct edge{int to,nxt;}e[N*2]; int hd[N],tot;
void add(int u,int v){e[++tot]=(edge){v,hd[u]};hd[u]=tot;}

int n,sz[N],msz[N];
void pre(int u,int fa){ //计算sz[u]和msz[u]
    for(int i=hd[u],v;i;i=e[i].nxt)
        if((v=e[i].to)!=fa){
            pre(v,u);
            sz[u]+=sz[v];
            if(sz[v]>sz[msz[u]]) msz[u]=v;
        }
    sz[u]++;// msz[u]=max(msz[u],n-sz[u]);
}

int f[N][2],mx[N]; 
void dfs1(int u,int fa){ //计算f[u][0/1]和mx[u] 
    for(int i=hd[u],v;i;i=e[i].nxt)
        if((v=e[i].to)!=fa){
            dfs1(v,u);
            int tmp=(sz[v]>n/2?f[v][0]:sz[v]);
            if(tmp>f[u][0]) f[u][1]=f[u][0],f[u][0]=tmp,mx[u]=v;
            else if(tmp>f[u][1]) f[u][1]=tmp;
        }
}

int g[N];
void dfs2(int u,int fa){ //计算 g[u] 
    for(int i=hd[u],v;i;i=e[i].nxt)
        if((v=e[i].to)!=fa){
            int tmp=(n-sz[v]>n/2?g[u]:n-sz[v]);
            g[v]=max(g[v],tmp);
            if(v==mx[u]) g[v]=max(g[v],f[u][1]);
            else g[v]=max(g[v],f[u][0]);
            dfs2(v,u);
        }
}

int main(){
    scanf("%d",&n);
    for(int i=1,u,v;i<n;i++)
        scanf("%d%d",&u,&v),add(u,v),add(v,u);
    pre(1,0), dfs1(1,0), dfs2(1,0);
    for(int i=1;i<=n;i++){
        bool centroid=1;
        if(sz[msz[i]]>n/2) centroid=(sz[msz[i]]-f[i][0]<=n/2);
        else if(n-sz[i]>n/2) centroid=(n-sz[i]-g[i]<=n/2);
        cout<<centroid<<" ";
    }
    return 0;
}