题意：
一个王国有n座城市，城市之间由n-1条道路相连，形成一个树结构，国王决定将一些城市设为重要城市。
这个国家有的时候会遭受外敌入侵，重要城市由于加强了防护，一定不会被占领。而非重要城市一旦被占领，这座城市就不能通行。
国王定了若干选择重要城市的计划，他想知道，对于每个计划，外敌至少要占领多少个非重要城市，才会导致重要城市之间两两不连通。如果外敌无论如何都不可能导致这种局面，输出-1。
题解：
考虑树形dp，首先考虑不行的情况，那么就是俩个相邻的点都是被标记的点，特判掉。然后fx表示以x为根的子树的答案，g[x]表示自己是否变为标记点。若x是标记点，则要让自己的儿子中有标记都选上。若x带有标记，若子节点带标记的大于等于2，则答案++。若只有一个儿子标记，那么标记保留。然后如果每次都dp的话，复杂度nq，肯定不行。考虑k的和很小，就把要用到的点，拿出来之后树形dp，这就用到了虚树的思想。
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 const int N = 2e5 + 10; 5 6 inline int read() 7 { 8 char ch = getchar();int x = 0, f = 1; 9 while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();} 10 while(ch >= '0' && ch <= '9') {x = (x << 1) + (x << 3) - '0' + ch; ch = getchar();} 11 return x * f; 12 } 13 14 int n, m, k; 15 int h[N], e[N], ne[N], idx, a[N]; 16 int size[N], son[N], top[N], d[N], f[N], dfn[N], num; 17 int stac[N], sz, vs[N]; 18 int dp[N]; 19 vector<int>g[N]; 20 void add(int a, int b) 21 { 22 e[idx] = b; 23 ne[idx] = h[a]; 24 h[a] = idx ++; 25 } 26 27 void dfs1(int u, int fa) 28 { 29 d[u] = d[fa] + 1; 30 f[u] = fa; 31 size[u] = 1; 32 for (int i = h[u]; ~i; i = ne[i]) 33 { 34 int j = e[i]; 35 if(j == fa) continue; 36 dfs1(j, u); 37 size[u] += size[j]; 38 if(size[son[u]] < size[j]) 39 son[u] = j; 40 } 41 } 42 43 void dfs2(int u, int tp) 44 { 45 top[u] = tp; 46 dfn[u] = ++ num; 47 if(son[u]) dfs2(son[u], tp); 48 for (int i = h[u]; ~i; i = ne[i]) 49 { 50 int j = e[i]; 51 if(j == son[u] || j == f[u]) continue; 52 dfs2(j, j); 53 } 54 } 55 56 int lca(int x, int y) 57 { 58 while(top[x] != top[y]) 59 { 60 if(d[top[x]] < d[top[y]]) swap(x, y); 61 x = f[top[x]]; 62 } 63 return d[x] < d[y] ? x : y; 64 } 65 66 bool cmp(int a, int b) 67 { 68 return dfn[a] < dfn[b]; 69 } 70 71 int dfs(int u) 72 { 73 int res = 0, mn = 0; 74 for (auto &j : g[u]) 75 { 76 res += dfs(j); 77 mn += dp[j]; 78 } 79 if(vs[u]) res += mn, dp[u] = 1; 80 else if(mn > 1) res ++, dp[u] = 0; 81 else dp[u] = mn; 82 g[u].clear(); vs[u] = 0; 83 return res; 84 } 85 86 int main() 87 { 88 n = read(); 89 for (int i = 1; i <= n; i ++) h[i] = -1; 90 for (int i = 1; i <= n - 1; i ++) 91 { 92 int a = read(), b = read(); 93 add(a, b); add(b, a); 94 } 95 dfs1(1, 0);dfs2(1, 1); 96 m = read(); 97 while(m --) 98 { 99 int flag = 1; 100 k = read(); 101 for (int i = 1; i <= k; i ++) a[i] = read(), vs[a[i]] = 1; 102 for (int i = 1; i <= k; i ++) 103 if(vs[a[i]] && vs[f[a[i]]]) 104 { 105 flag = 0; 106 break; 107 } 108 if(!flag) 109 { 110 for (int i = 1; i <= k; i ++) 111 vs[a[i]] = 0; 112 puts("-1"); 113 continue; 114 } 115 sort(a + 1, a + k + 1, cmp); 116 sz = 0; 117 stac[++ sz] = a[1]; 118 for (int i = 2; i <= k; i ++) 119 { 120 int z = lca(stac[sz], a[i]); 121 while(d[z] < d[stac[sz - 1]]) 122 { 123 g[stac[sz - 1]].push_back(stac[sz]); 124 sz --; 125 } 126 if(z != stac[sz]) 127 { 128 g[z].push_back(stac[sz]); 129 if(z == stac[sz - 1]) sz --; 130 else stac[sz] = z; 131 } 132 stac[++ sz] = a[i]; 133 } 134 while(-- sz) g[stac[sz]].push_back(stac[sz + 1]); 135 printf("%d ", dfs(stac[1])); 136 } 137 }