做到了一个没见过的idea的题，幸甚至哉，歌以咏志。
------------------
题目大意：给定一颗树，你有一次将树改造的机会，改造的意思是删去一条边，再加入一条边，保证改造后还是一棵树。请问有多少点可以通过改造，成为这颗树的重心？
首先有一个显然的事实：如果一个点是原本树的中心，那么不用管它；如果这个点经过改造后可以成为树的重心，那么必然有且只有一个子树的大小大于$lfloor frac{n}{2} floor$。而我们改造这个点的方法是：找这个重儿子最大的小于等于$lfloor frac{n}{2} floor$的子树，并将它插到这个点上。
所以我们要DP来求上述这个子树的大小。设$f_i$表示最大的小于等于$lfloor frac{n}{2} floor$的子树的大小。有转移：
$f_u=max(size_v) (size_v < lfloor frac{n}{2} floor)$
$f_u=max(f_v) (size_v > lfloor frac{n}{2} floor)$
同时我们设$g_u$表示$f_u$所指的$u$。上述的操作都可以$O(n)$解决。这样我们就解决了子树内的情况。
对于子树外的点，我们设$h_i$表示不在子树中的最大取值。有转移：
$h_v=max(n-size_u) (n-size_u < lfloor frac{n}{2} floor)$
$h_v=max(h_u) (n-size_u > lfloor frac{n}{2} floor)$
如果$f_u$的最佳转移点是$v$，那么$h_v$与$f_u$的次大值取$max$；反则与最大值取$max$。
最后判断是否合法：如果重儿子大小大于$lfloor frac{n}{2} floor$，那么就看重儿子大小减去$f_{son_u}$是否小于等于$lfloor frac{n}{2} floor$；若$n-size_u > lfloor frac{n}{2} floor$，那么看$n-size_u$与$h_u$的差值是否小于等于$lfloor frac{n}{2} floor$。
时间复杂度$O(n)$。
代码：
#include<cstdio> #include<iostream> using namespace std; const int maxn=400005; int f[maxn][2],g[maxn],h[maxn],son[maxn],size[maxn],ans[maxn],n; int head[maxn],cnt; struct node { int next,to; }edge[maxn*2]; inline int read() { int x=0,f=1;char ch=getchar(); while(!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();} while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();} return x*f; } inline void add(int from,int to) { edge[++cnt].next=head[from]; edge[cnt].to=to; head[from]=cnt; } inline void dfs_pre(int now,int fa) { size[now]=1; for (int i=head[now];i;i=edge[i].next) { int to=edge[i].to; if (to==fa) continue; dfs_pre(to,now); size[now]+=size[to]; if (size[to]>size[son[now]]) son[now]=to; int cur=(size[to]<=n/2)?size[to]:f[to][0]; if (cur>f[now][0]) { f[now][1]=f[now][0]; f[now][0]=cur; g[now]=to; } else if (cur>f[now][1]) f[now][1]=cur; } } inline void dfs_dp(int now,int fa) { ans[now]=1; if (size[son[now]]>n/2) ans[now]=size[son[now]]-f[son[now]][0]<=n/2; else if (n-size[now]>n/2) ans[now]=n-size[now]-h[now]<=n/2; for (int i=head[now];i;i=edge[i].next) { int to=edge[i].to; if (to==fa) continue; int cur = n-size[now] <= n/2 ? n-size[now] : h[now]; h[to]=max(h[to],cur); h[to]=max(h[to],f[now][g[now]==to]); dfs_dp(to,now); } } int main() { n=read(); for (int i=1;i<n;i++) { int x=read(),y=read(); add(x,y);add(y,x); } dfs_pre(1,0); dfs_dp(1,0); for (int i=1;i<=n;i++) printf("%d ",ans[i]); return 0; }