其实这道题换根的时候不需要再维护一个次大值，提供一种维护重儿子的做法。
我们来考虑暴力怎么做？
枚举每个点，如果它的最大的子树都不大于(frac{n}{2})的话那它肯定可以（已经可以那断一条边再连上即可）。注意这里是不大于所以直接下取整对答案没有影响。
先统计一遍大于(frac{n}{2})的子树的个数，首先这个个数肯定不会大于(1)（这不废话吗？）。然后对于那个大于(frac{n}{2})的儿子，它肯定是子树大小最大的儿子，这不就是重链剖分中的重儿子吗？所以我们每个点还可以记录一个重儿子。
下文删掉的意思是将其连向父亲的边删掉然后连向根节点。
如果一个点的重儿子将其重儿子的子树删掉后还没有小于等于(frac{n}{2})那么显然这个点就不行。
那如果满足情况呢？我们发现如果其本身大小也大于(frac{n}{2})的话也不行。那如果删其他儿子的话一定也会大于(frac{n}{2})了（因为重儿子已经大于(frac{n}{2})），所以一定还得删重儿子的儿子，同理最优还是删重儿子的重儿子（有点绕...），而如果不行则删其他儿子也不行。
故我们需要在重链上找一个子树大小小于等于(frac{n}{2})的点，而这个点必然越浅越好（子树大小越大越好）。这样我们将重链放在一个set中维护然后找到第一个小于等于(frac{n}{2})的点，判断减去它能否小于(frac{n}{2})即可。
然后各种DS套上去就行了，但是我们不想写DS怎么办（其实是我不会），其实就是求一个子树内子树大小小于等于(frac{n}{2})且最大的点，这不是dp就好了吗？（这也是为什么这题难度是蓝的原因）
设(dp_x)为(x)子树内子树大小小于等于(frac{n}{2})且最大的点的子树大小（不包括(x)），则根据上面的推导有(dp_x=max(dp_{son_x}, size_{son_x}(size_{son_x} le frac{n}{2})))。其中(son_x)代表(x)的重儿子。
然后换根求dp值，按我上面的做法判断即可。
具体怎么换根呢？
如果我们现在想要把根从(x)换成(y)，可以分成两类讨论。
首先不管哪一类都要将(x)和(y)的(size)改变，具体实现就是换根dp的基础了吧。
第一种情况：(y)不是(x)的重儿子。那这种情况(x)的重儿子不会改变，只要判断(y)的重儿子有没有改成(x)，然后更新(y)的重儿子与dp值。
第二种情况：(y)是(x)的重儿子。此时(x)的重儿子会改变（变成除了(y)以外与(x)相连的一个点），那么只要遍历一遍与(x)相邻的点重新求一下(x)的重心并更新dp值。重复情况一(y)的更新。
时间复杂度：(O(n+m))，因为只有一个重儿子所以遍历也只会遍历一遍，又每个边也只会被遍历两遍所以总的时间复杂度是(O(m))级别的。
Code：
#include <bits/stdc++.h>
using namespace std;
const int N = 400010;
namespace IO{
template <typename T> void read(T &x) {
T f = 1;
char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
for (x = 0; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
x *= f;
}
} using namespace IO;
namespace ZCR{
struct node{
int pre, to;
}edge[N << 1];
int head[N], tot;
int n, goal;
int dp[N], sz[N], son[N];
int ans[N];
void add(int u, int v) {
edge[++tot] = node{head[u], v};
head[u] = tot;
}
void change(int x) {
if (son[x]) {
dp[x] = dp[son[x]];
if (sz[son[x]] <= goal) dp[x] = sz[son[x]];
}
}
void dfs1(int x, int fa) {
sz[x] = 1;
for (int i = head[x]; i; i = edge[i].pre) {
int y = edge[i].to;
if (y == fa) continue;
dfs1(y, x);
sz[x] += sz[y];
if (sz[y] > sz[son[x]]) son[x] = y;
}
change(x);
}
void change_root(int x, int y) {
sz[x] -= sz[y];
sz[y] += sz[x];
if (y == son[x]) {
son[x] = 0;
for (int i = head[x]; i; i = edge[i].pre) {
int z = edge[i].to;
if (z == y) continue;
if (sz[z] > sz[son[x]]) son[x] = z;
}
change(x);
}
if (sz[son[y]] < sz[x]) {
son[y] = x;
change(y);
}
}
void dfs2(int x, int fa) {
if (sz[son[x]] <= goal || sz[son[x]] - dp[son[x]] <= goal) ans[x] = true;
for (int i = head[x]; i; i = edge[i].pre) {
int y = edge[i].to;
if (y == fa) continue;
change_root(x, y);
dfs2(y, x);
change_root(y, x);
}
}
void MAIN() {
memset(dp, 0xcf, sizeof(dp));
read(n);
goal = n / 2;
for (int i = 1, u, v; i < n; i++) {
read(u); read(v);
add(u, v);
add(v, u);
}
dfs1(1, 0);
dfs2(1, 0);
for (int i = 1; i <= n; i++) printf("%d ", ans[i]);
}
} using namespace ZCR;
int main() {
MAIN();
return 0;
}
一遍过了好开心(@^▽^@)