C. Centroids
time limit per test
memory limit per test
input
output
Tree is a connected acyclic graph. Suppose you are given a tree consisting of n vertices. The vertex of this tree is called centroid if the size of each connected component that appears if this vertex is removed from the tree doesn't exceed
.
n and can perform no more than one edge replacement. Edge replacement
Input
n (2 ≤ n ≤ 400 000) — the number of vertices in the tree. Each of the next n - 1 lines contains a pair of vertex indices ui and vi (1 ≤ ui, vi ≤ n) — endpoints of the corresponding edge.
Output
n integers. The i-th of them should be equal to 1 if the i-th vertex can be made centroid by replacing no more than one edge, and should be equal to 0
Examples
input
31 2 2 3
output
1 1 1
input
51 2 1 3 1 4 1 5
output
1 0 0 0 0
某大牛思路:先找到树的重心，然后以重心为根重新建树，这样每根的每个儿子节点的节点个数都不会比n/2大，在判断每一个节点的时候，先判断他是不是来自根节点节点数最多的那棵子树，如果是，就判断他是那个面的点减去根节点次大的子树结点个数是不是大于n/2，小于就说明可以改为重心
同样的，如果这个节点不是来自根节点最大的那一颗子树，那么就判断它如果把根节点最大的一颗子树接到他的上面那么他会不会成为重心
大概就是这样，算法时间复杂度O（n）
#include <bits/stdc++.h>
#define maxn 400005
using namespace std;
typedef long long ll;
int dp[maxn], ans[maxn], mins = 1e9, e, k;
int n, k1, k2, u, kk;
vector<int> v[maxn];
struct Node{
Node(int a, int b){
p = a;
i = b;
}
friend bool operator < (const Node&a, const Node&b){
return a.p > b.p;
}
int p, i;
};
void dfs1(int j, int f){
dp[j] = 1;
int maxs = 0;
for(int i = 0; i < v[j].size(); i++){
int h = v[j][i];
if(h != f){
dfs1(h, j);
maxs = max(maxs, dp[h]);
dp[j] += dp[h];
}
}
maxs = max(maxs, n - dp[j]);
if(mins > maxs){
mins = maxs;
e = j;
k = f;
}
}
void dfs2(int j, int f){
dp[j] = 1;
if(j == u)
kk = k2;
for(int i = 0; i < v[j].size(); i++){
int h = v[j][i];
if(h != f){
dfs2(h, j);
dp[j] += dp[h];
}
}
int m = n - dp[j];
if(m <= n/2)
ans[j] = 1;
else if(m - kk <= n / 2)
ans[j] = 1;
if(j == u)
kk = k1;
}
int main(){
// freopen("in.txt", "r", stdin);
int a, b;
scanf("%d", &n);
for(int i = 0; i < n - 1; i++){
scanf("%d%d", &a, &b);
v[a].push_back(b);
v[b].push_back(a);
}
dfs1(1, -1);
vector<Node> h;
for(int i = 0; i < v[e].size(); i++){
if(v[e][i] != k){
h.push_back(Node(dp[v[e][i]], v[e][i]));
}
else
h.push_back(Node(n-dp[e], k));
}
sort(h.begin(), h.end());
if(n % 2 == 0 && h[0].p == n / 2){
k1 = n / 2;
k2 = n / 2;
u = h[0].i;
}
else{
k1 = h[0].p;
k2 = h[1].p;
u = h[0].i;
}
kk = k1;
dfs2(e, -1);
printf("%d", ans[1]);
for(int i = 2; i <= n; i++)
printf(" %d", ans[i]);
puts("");
return 0;
}