Interesting Vertices

参考博客：https://blog.csdn.net/I_believe_CWJ/article/details/102472012

题目大意：给你一课有n个节点的树，其中有k个节点被染色，求有多少个节点满足自身没有被染色
并且它的每棵子树中都至少有一个节点被染色。
解题思路：dfs回溯类似求树的重心的方式求解，dfsdfs回溯可以得到每个节点的它的子树中是否都有染色的点
并统计所有子树中染色点的个数sum，然后走向父亲的那棵子树中被染色的点数就为k−sum，
这样即可判断此节点是否满足条件。

AC_Code

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <ctime>
 5 #include <cmath>
 6 #include <vector>
 7 #include <map>
 8 #include <vector>
 9 #include <algorithm>
10 #define bug printf("*********
");
11 #define mem0(a) memset(a, 0, sizeof(a));
12 #define mem1(a) memset(a, -1, sizeof(a));
13 #define ios ios::sync_with_stdio(false);
14 #define pb(x) push_back(x)
15 using namespace std;
16 typedef long long LL;
17 const LL mod = 1e9 + 7;
18 const int inf = 1e9 + 7;
19 const LL INF = 1e18 + 7;
20 const double eps = acos(-1.0);
21 
22 int n, k, cnt;
23 int c[200010];///标记是否是染色点
24 int head[200010];///前向星使用
25 int vis[200010];///标记是否访问过
26 int sz[200010];///sz[i]表示第i个节点的子树中一共有多少个被染色
27 
28 struct edge {
29     int to, nxt;
30 }e[200010*2];
31 
32 void add(int u, int v) {
33     e[cnt].to = v;
34     e[cnt].nxt = head[u];
35     head[u] = cnt ++;
36 }
37 
38 vector<int> ans;
39 
40 void dfs(int u) {
41     vis[u] = 1;
42     sz[u] = c[u];
43     int flag = 1;
44     for(int i = head[u]; ~i; i = e[i].nxt) {
45         int en = e[i].to;
46         if(vis[en]) continue;
47         dfs(en);
48         if(!sz[en]) flag = 0;///此子树没有被染色
49         sz[u] += sz[en];
50     }
51     ///k-sz[u]>0 是指u的父亲节点所带领的那棵子树有被染色
52     ///！c[u]是指满足改点没有被染色
53     ///flag表示点的所有子树都有被染色
54     ///u==1是因为1节点没有父亲节点了
55     if(!c[u] && flag && (k-sz[u]>0 || u == 1)) ans.pb(u);
56 }
57 
58 int main() {
59     int x, y;
60     while(~scanf("%d%d", &n, &k)) {
61         mem0(vis);mem0(c);mem1(head);
62         cnt = 0;
63         ans.clear();
64         for(int i = 0; i < k; i ++) {
65             scanf("%d", &x);
66             c[x] = 1;
67         }
68         for(int i = 0; i < n-1; i ++) {
69             scanf("%d%d", &x, &y);
70             add(x, y), add(y, x);
71         }
72         dfs(1);///假装以1为树的总根
73         sort(ans.begin(), ans.end());
74         printf("%d
", ans.size());
75         for(auto i : ans) {
76             printf("%d ", i);
77         }
78         printf("
");
79     }
80     return 0;
81 }