Codeforces708C Centroids 【树形dp】

题目链接

题意:给定一棵n个结点的树,问:对于每个结点,能否通过删除一条边并添加一条边使得仍是树,并且删除该结点后得到的各个连通分量结点数 <= n/2?

题解:树形dp,两遍dfs,第一遍dfs求得以各个结点为根的子树的结点数,以及各个结点下面切掉某条边后最多可切出多少个结点;

          第二遍dfs求得每个结点上面切掉某条边后最多可切出多少个结点。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define X first
 4 #define Y second
 5 typedef long long ll;
 6 const int N = 4e5+1;
 7 vector<int> ve[N];
 8 int num[N], maxson[N], down[N], up[N];
 9 int n;
10 void gmax(int& a, int b){ if(a < b) a = b;}
11 void dfs(int x, int fa){
12 //    printf("dfs x %d, fa %d
", x, fa);
13     num[x] = 1;
14     down[x] = maxson[x] = 0;
15     for(int i = 0; i < ve[x].size(); i++){
16         int y = ve[x][i];
17         if(y == fa) continue ;
18         dfs(y, x);
19         num[x] += num[y];
20         gmax(down[x], num[y] <= n/2? num[y]: down[y]);
21         gmax(maxson[x], num[y]);
22     }
23 }
24 multiset<int>::iterator it;
25 void dfs2(int x, int fa){
26 //    printf("dfs2 x %d, fa %d
", x, fa);
27     multiset<int> se;
28     for(int i = 0; i < ve[x].size(); i++){
29         int y = ve[x][i];
30         if(y != fa) se.insert( num[y] <= n/2? num[y]:down[y] );
31     }
32 
33     for(int i = 0; i < ve[x].size(); i++){
34         int y = ve[x][i];
35         if(y != fa){
36             if(n-num[y] <= n/2)
37                 up[y] = n-num[y];
38             else {
39                 it = se.find( num[y] <= n/2? num[y]:down[y] );
40                 se.erase(it);
41                 gmax(up[y], up[x]);
42                 if(!se.empty())
43                     gmax(up[y], *se.rbegin());
44                 se.insert( num[y] <= n/2? num[y]:down[y] );
45             }
46             dfs2(y, x);
47         }
48     }
49 }
50 
51 int main(){
52     int u, v; scanf("%d", &n);
53     for(int i = 1; i < n; i++){
54         scanf("%d%d", &u, &v);
55         ve[u].push_back(v), ve[v].push_back(u);
56     }
57     dfs(1, -1);
58     dfs2(1, -1);
59     bool tag;
60 //    for(int i = 1; i <= n; i++)
61 //        cout << maxson[i] << ' ' << num[i] << ' ' << down[i] << ' ' << up[i] << endl;
62     for(int i = 1; i <= n; i++){
63         if(maxson[i] <= n/2&&n-num[i] <= n/2)//不用切
64             tag = true;
65         else if(n-num[i] > n/2)//要切上面
66             tag = n-num[i]-up[i] <= n/2;
67         else//要切下面
68             tag = maxson[i]-down[i] <= n/2;
69         putchar(tag+'0');
70         putchar(i == n? '
':' ');
71     }
72     return 0;
73 }
原文地址:https://www.cnblogs.com/dirge/p/5960580.html