题意:给定一棵n个结点的树,问:对于每个结点,能否通过删除一条边并添加一条边使得仍是树,并且删除该结点后得到的各个连通分量结点数 <= n/2?
题解:树形dp,两遍dfs,第一遍dfs求得以各个结点为根的子树的结点数,以及各个结点下面切掉某条边后最多可切出多少个结点;
第二遍dfs求得每个结点上面切掉某条边后最多可切出多少个结点。
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
typedef long long ll;
const int N = 4e5+;
vector<int> ve[N];
int num[N], maxson[N], down[N], up[N];
int n;
void gmax(int& a, int b){ if(a < b) a = b;}
void dfs(int x, int fa){
// printf("dfs x %d, fa %d\n", x, fa);
num[x] = ;
down[x] = maxson[x] = ;
for(int i = ; i < ve[x].size(); i++){
int y = ve[x][i];
if(y == fa) continue ;
dfs(y, x);
num[x] += num[y];
gmax(down[x], num[y] <= n/? num[y]: down[y]);
gmax(maxson[x], num[y]);
}
}
multiset<int>::iterator it;
void dfs2(int x, int fa){
// printf("dfs2 x %d, fa %d\n", x, fa);
multiset<int> se;
for(int i = ; i < ve[x].size(); i++){
int y = ve[x][i];
if(y != fa) se.insert( num[y] <= n/? num[y]:down[y] );
} for(int i = ; i < ve[x].size(); i++){
int y = ve[x][i];
if(y != fa){
if(n-num[y] <= n/)
up[y] = n-num[y];
else {
it = se.find( num[y] <= n/? num[y]:down[y] );
se.erase(it);
gmax(up[y], up[x]);
if(!se.empty())
gmax(up[y], *se.rbegin());
se.insert( num[y] <= n/? num[y]:down[y] );
}
dfs2(y, x);
}
}
} int main(){
int u, v; scanf("%d", &n);
for(int i = ; i < n; i++){
scanf("%d%d", &u, &v);
ve[u].push_back(v), ve[v].push_back(u);
}
dfs(, -);
dfs2(, -);
bool tag;
// for(int i = 1; i <= n; i++)
// cout << maxson[i] << ' ' << num[i] << ' ' << down[i] << ' ' << up[i] << endl;
for(int i = ; i <= n; i++){
if(maxson[i] <= n/&&n-num[i] <= n/)//不用切
tag = true;
else if(n-num[i] > n/)//要切上面
tag = n-num[i]-up[i] <= n/;
else//要切下面
tag = maxson[i]-down[i] <= n/;
putchar(tag+'');
putchar(i == n? '\n':' ');
}
return ;
}