CF708C Centroids

先考虑以为根的情况

考虑到至多只有一个的子树，我们肯定找是中那个最大的的子树，然后扣下来接到上面，再判断能否成为重心，即

我们考虑如何维护这个过程，我们先维护最大的儿子，然后求每个内最大的的子树，记为和

这样就把问题转化成

我们考虑换根解决剩下的部分，我们还需要维护的补树中的，传给

，的此时显然为中的次大子树中的，所以这启示我们还需要维护一个次大的内的子树大小
，的此时显然为

记这个

并且上述的要和取个最大值

#include<bits/stdc++.h>
#define pt putchar(' ')
#define nl puts("")
#define pi pair<int,int>
#define pb push_back
#define go(it) for(auto &it:as[x])
using namespace std;

const int N=4e5+10;
int n,u,v;
int sz[N],f[N],g[N],h[N],son[N],bel[N],ans[N];
vector<int> as[N];

int fr(){
    int x=0,flag=1;
    char ch=getchar();
    while(ch<'0' || ch>'9'){
        if(ch=='-') flag=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9'){
        x=x*10+(ch-'0');
        ch=getchar();
    }
    return x*flag;
}
void fw(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) fw(x/10);
    putchar(x%10+'0');
}
int max(int a,int b){return a>b?a:b;}
int min(int a,int b){return a<b?a:b;}

void prework(int x,int rt)
{
    sz[x]=1;
    go(v)
    {
        if(v==rt) continue;
        prework(v,x);
        sz[x]+=sz[v];
        if(sz[son[x]]<sz[v]) son[x]=v;
        int val=(sz[v]<=n/2)?sz[v]:f[v];
        if(val>f[x]) g[x]=f[x],f[x]=val,bel[x]=v;
        else g[x]=max(g[x],val);
    }
}

void dfs(int x,int rt)
{
    ans[x]=1;
    if(n-sz[x]>n/2 && n-sz[x]-h[x]>n/2) ans[x]=0;
    if(sz[son[x]]>n/2 && sz[son[x]]-f[son[x]]>n/2) ans[x]=0;
    
    go(v)
    {
        if(v==rt) continue;
        h[v]=(n-sz[x]<=n/2)?(n-sz[x]):h[x];
        
        if(v==bel[x]) h[v]=max(h[v],g[x]); //最大子树
        else h[v]=max(h[v],f[x]);
        dfs(v,x);
    }
}

int main()
{
    n=fr();
    for(int i=1;i<n;i++)
    {
        u=fr(),v=fr();
        as[u].pb(v),as[v].pb(u);
    }
    
    prework(1,0);
    dfs(1,0);
    for(int i=1;i<=n;i++)
        fw(ans[i]),pt;
    
    return 0;
}