CF708C Centroids

一道换根 DP。

我们可以先找出树的一个重心，那么对于其他所有不是重心的点，它不能成为重心时因为它父亲的那一支节点数大于一半，而可以改造成功，则意味着可以在他父亲那一支里，可以找到子树u，使 $siz[u] \le n/2$ && $siz[fa]-siz[u] \le n/2 $ 。简而言之，就是对于每个节点，我们要找除了节点本身以外的部分中不超出 $\left \lfloor \frac{n}{2}  \right \rfloor$  的最大子树大小，我们记为cut（u），接下来就是换根dp。

 我们用 $Max[u][0/1]$ 记录子树u中最大/次大的子树大小，maxx为u的祖先节点中最大的子树大小（dfs的时候带的参数）。

$\left\{\begin{matrix}cut[v]= \max(maxx,Max[u][0]),if(siz[v]!=Max[u][0]) \\cut[v]=max(maxx,Max[u][1]),if(siz[v]!=Max[u][0])\end{matrix}\right. $ 

对于每一个节点 $u$，我们只需要看 $N-siz[u]-cut[u]\le\left \lfloor \frac{N}{2}  \right \rfloor  $ 是否成立即可。

#include<bits/stdc++.h>
using namespace std;
const int N=8e5+5;
struct edge{
    int to,nex;
}e[N];
int cnt,h[N],n,siz[N],Max[N][3];
void adda(int u,int v){
    e[++cnt].nex=h[u];e[cnt].to=v;h[u]=cnt;
}
int rt,fa[N];
void dfs1(int u,int fath){
    bool p=1;
    siz[u]=1;
    for(int i=h[u];i;i=e[i].nex){
        int v=e[i].to;
        if(v==fath) continue; 
        dfs1(v,u);
        //if(siz[v]<=n/2) Max[u]=max(Max[u],siz[v]);
        siz[u]+=siz[v];
        if(siz[v]>(n/2)) p=0;
    }
    if(n-siz[u]>(n/2)) p=0;
    if(p) rt=u;
    return;
}
void dfs2(int u,int fath){
    fa[u]=fath;
    siz[u]=1;
    for(int i=h[u];i;i=e[i].nex){
        int v=e[i].to;
        if(v==fath) continue;
        dfs2(v,u);
        siz[u]+=siz[v];
        if(siz[v]>n/2) continue;
        if(siz[v]>Max[u][0]) Max[u][1]=Max[u][0],Max[u][0]=siz[v];
        else if(siz[v]>Max[u][1]) Max[u][1]=siz[v];
    }
}
int cut[N];
bool ans[N];
void dfs3(int u,int maxx){
    cut[u]=maxx;
    if(n-siz[u]-cut[u]<=n/2) ans[u]=1;
    if(n-siz[u]<=n/2) maxx=max(maxx,n-siz[u]);
    for(int i=h[u];i;i=e[i].nex){
        int v=e[i].to;
        if(v==fa[u]) continue;
        //dfs3(v,maxx);
        if(siz[v]==Max[u][0]) dfs3(v,max(maxx,Max[u][1]));
        else dfs3(v,max(maxx,Max[u][0]));
    }
}
int main(){
    cin>>n;
    for(int i=1,u,v;i<n;i++){
        scanf("%d%d",&u,&v);
        adda(u,v);adda(v,u);
    }
    dfs1(1,0);
    ans[rt]=1;
    //cout<<rt;
    dfs2(rt,0);
    dfs3(rt,0);
    for(int i=1;i<=n;i++){
        if(ans[i]) printf("1 ");
        else printf("0 ");
    }
}