确实不简单。
首先要理解题意。你可以拿掉任意一棵子树,接到一个节点上,但是拿掉的子树的大小并不是1~siz[u]。假设树根为root,我们找到子树中最大的子树,从中拿掉最大的小子树,然后接到根上,
如果这个时候符合题意,那么以root为根就可以通过改造成为树的重心。
问题的关键就是求出以root为根时,root的每个儿子能拿掉的子树大小的最大值是多少。可以用树形DP,算两次。
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int N = 4e5 + 100;
int head[N], cnt, siz[N], wgt[N];
int n;
int dw1[N], dw2[N], p1[N], up[N], mor[N], idx[N];//mor[u]:以u为根的子树中,大于 n / 2的子树有多少个
bool ans[N]; //idx[u]最大子树的编号
struct Edge {
int v, nxt;
} e[N <<1];
void AddEdge(int u, int v) {
e[++cnt].v = v;
e[cnt].nxt = head[u];
head[u] = cnt;
}
void update(int u, int v, int val) {
if( val > n / 2) {
mor[u] ++;
return;
}
if( val >= dw1[u]) {
dw2[u] = dw1[u];
p1[u] = v;
dw1[u] = val;
}
else if( val > dw2[u])
dw2[u] = val;
}
void dfs1(int u, int fa) {
siz[u] = 1;
int wgt = 0;
for(int i = head[u]; i; i = e[i].nxt) {
int v = e[i].v;
if( v == fa) continue;
dfs1(v, u);
siz[u] += siz[v];//dw1[u]:以u为根的子树中,满足siz <= n / 2的最大值
if(siz[v] <= n / 2)
update(u, v, max(dw1[v], siz[v]));//!!!
else
update(u, v, dw1[v]);
if( siz[v] > wgt)
idx[u] = v, wgt = siz[v];
if( siz[v] > n / 2)
mor[u] ++;
}
if( n - siz[u] <= n / 2) {
up[u] = n - siz[u];
}
else
mor[u] ++;
if( n - siz[u] > wgt)
idx[u] = n + 1;//上方子树
}
void dfs2(int u, int fa) {
for(int i = head[u]; i; i = e[i].nxt) {
int v = e[i].v;
if( v == fa) continue;
/* if(v == 6) {
printf("D: %d %d\n", dw1[u], p1[u]);
} */
if(p1[u] != v) {
up[v] = max(up[v], max(dw1[u], up[u]));
}
else up[v] = max(up[v], max(dw2[u], up[u]));
dfs2(v, u);
}
if(mor[u] > 1) ans[u] = false;
else if( mor[u] == 0) ans[u] = true;
else {
if( idx[u] == n + 1) {
ans[u] = ( (n - siz[u]) - up[u]) <= n / 2;
}
else {
ans[u] = (siz[idx[u]] - dw1[u]) <= n / 2;
}
}
}
int main()
{
// freopen("E:\\data.in.txt", "r", stdin);
scanf("%d", &n);
for(int i = 1; i < n; i ++) {
int u, v;
scanf("%d%d", &u, &v);
AddEdge(u, v), AddEdge(v, u);
}
dfs1(1, 0);
dfs2(1, 0);
for(int i = 1; i <= n; i ++) {
printf("%d ", ans[i]);
}
return 0;
}