Description
Given a tree.
At most one operation is performed: an edge is deleted and a new edge is connected, ensuring that the tree remains after the operation.
Ask whether each point can become the center of gravity of the tree after the operation.
Solution
characteristic\(1\): If a point is not the center of gravity of a tree, it must have a size greater than\(\lfloor n/2\rfloor\) of the subtree.
characteristic\(2\): If a point is legal, either it was originally the center of gravity or it has only one subtree larger than the\(\lfloor n/2\rfloor\)and removes from this subtree a maximum of less than or equal to\(\lfloor n/2\rfloor\) of a subtree can be made such that it itself is also less than or equal to\(\lfloor n/2\rfloor\)。
Consider Tree dp, set\(f(u)\) expressed in terms of\(u\) The largest of the subtrees rooted at no more than\(\lfloor n/2\rfloor\) The size of the subtree, initially starting with\(1\) is the total root, transferred as follows.
(coll.) fail (a student)\(size_v\le \lfloor n/2\rfloor\) when\(f(u) = \max(f(u),size_v)\)，
if not\(f(u) = \max(f(u),f(v))\)，
\(v\in son_u\)。
Consider how to handle the answer outside the subtree, i.e., root swapping, and let\(g(u)\) away\(u\) is the answer within the subtree of the root.
To facilitate the transfer, we need to change the state\(f\)set up\(f(u,0/1)\) denoting the largest answer and the next largest answer, respectively, with transfers similar to the original, and then also keeping track of the best transfer state for each point, that is, the point from which it was ultimately transferred.
\(g\) The transfers are as follows.
(coll.) fail (a student)\(f(u,0)\) The optimal transfer of the\(v\) when
- in the event that\(n-size_u\le \lfloor n/2\rfloor\)So.\(g(v) = \max(g(u),n-size_u,f(u,1))\)，
- if not\(g(v) = \max(g(u),f(u,1))\)，
Otherwise.
- in the event that\(n-size_u\le \lfloor n/2\rfloor\)So.\(g(v) = \max(g(u),n-size_u,f(u,0))\)，
- if not\(g(v) = \max(g(u),f(u,0))\)。
Ultimately, depending on the nature\(2\), it is sufficient to determine whether each point is legal or not.
Code
const int N = 4e5 + 5;
int n;
vector <int> e[N];
int siz[N], f[N][2], mx[N]; // f(u) : in order to u within a subtree rooted at the root satisfies the size <=n/2 The size of the largest and second largest subtrees of (整棵树in order to 1 get at)
// mx(u) : record (in sports etc) f(u) Optimal transfer of v
int g[N];
bool ans[N];
void dfsF(int u, int fa){
siz[u] = 1;
for(int v : e[u]){
if(v == fa) continue;
dfsF(v, u);
siz[u] += siz[v];
if(siz[v] <= n / 2){
if(siz[v] > f[u][0]){ // Maximum and next largest cannot be transferred from the same subtree！
f[u][1] = f[u][0];
f[u][0] = siz[v];
mx[u] = v;
}else if(siz[v] > f[u][1]) f[u][1] = siz[v];
}
else{
if(f[v][0] > f[u][0]){
f[u][1] = f[u][0];
f[u][0] = f[v][0];
mx[u] = v;
}else if(f[v][0] > f[u][1]) f[u][1] = f[v][0];
}
}
}
void dfsG(int u, int fa){
for(int v : e[u]){
if(v == fa) continue;
if(mx[u] == v){
if(n - siz[u] <= n / 2) g[v] = max(f[u][1], n - siz[u]);
else g[v] = max(f[u][1], g[u]);
}else{
if(n - siz[u] <= n / 2) g[v] = max(f[u][0], n - siz[u]);
else g[v] = max(f[u][0], g[u]);
}
dfsG(v, u);
}
}
void dfsAns(int u, int fa){
int mx = n - siz[u];
int cnt = 0, id = -1;
if(mx > n / 2) id = fa, cnt++;
for(int v : e[u]){
if(v == fa) continue;
if(siz[v] > n / 2){
mx = siz[v];
id = v;
cnt++;
}
dfsAns(v, u);
}
if(cnt == 0) ans[u] = true;
else if(cnt == 1 && id == fa && mx - g[u] <= n / 2) ans[u] = true;
else if(cnt == 1 && id != fa && mx - f[id][0] <= n / 2) ans[u] = true;
else ans[u] = false;
}
void Solve(){
cin >> n;
int u, v;
for(int i = 1; i <= n - 1; i++){
cin >> u >> v;
e[u].ps(v);
e[v].ps(u);
}
dfsF(1, 0);
dfsG(1, 0);
dfsAns(1, 0);
for(int i = 1; i <= n; i++) cout << ans[i] << ' ';
}