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 "); } }