【题意】：给出一棵树，每个节点代表一台电脑，现在需要选择一些电脑作为服务器。如果一台电脑被选作服务器，那么它和和它相邻的电脑都会被激活，非服务器的电脑不能同时被多台服务器激活。问最少要选多少台电脑作为服务器使得所有电脑被激活。
【题解】：树dp，树的最小支配集变形。
设状态
dp[u][0] 以u为根且u为服务器且整棵子树都被激活的最小代价。
dp[u][1] 以u为根且u被某个儿子结点激活且整棵子树都被激活的最小代价。
dp[u][2] 以u为根且u被父亲结点激活且整棵子树都被激活的最小代价。
转移 (v 为 u 的儿子)
dp[u][0] = ∑min(dp[v][0], dp[v][2]) + 1;
dp[u][1] = min(sum - dp[v][1] + dp[v][0]), sum = ∑dp[v][1];
dp[u][2] = ∑dp[v][1];
任取一个结点为root进行树dp, ans = min(dp[root][0], dp[root][1]).
【代码】：
1 #include "iostream"
2 #include "cstdio"
3 #include "cstring"
4 #include "algorithm"
5 #include "vector"
6 #include "queue"
7 #include "cmath"
8 #include "string"
9 #include "cctype"
10 #include "map"
11 #include "iomanip"
12 using namespace std;
13 #define pb push_back
14 #define mp make_pair
15 #define fi first
16 #define se second
17 #define lc(x) (x << 1)
18 #define rc(x) (x << 1 | 1)
19 #define lowbit(x) (x & (-x))
20 #define ll long long
21 #define maxn 10050
22 const int inf = 1 << 20;
23 vector<int> vec[maxn];
24 int n, dp[maxn][3];
25
26 void dfs(int u, int fa) {
27 int size = vec[u].size();
28 dp[u][0] = 1;
29 dp[u][1] = inf;
30 dp[u][2] = 0;
31 for(int i = 0; i < size; i++) {
32 int v = vec[u][i];
33 if(v == fa) continue;
34 dfs(v, u);
35 dp[u][0] += min(dp[v][2], dp[v][0]);
36 dp[u][2] += dp[v][1];
37 }
38 for(int i = 0; i < size; i++) {
39 int v = vec[u][i];
40 if(v == fa) continue;
41 dp[u][1] = min(dp[u][1], dp[u][2] - dp[v][1] + dp[v][0]);
42 }
43 }
44
45 int main() {
46 int symbol = 0;
47 while(symbol != -1) {
48 scanf("%d", &n);
49 for(int i = 0; i < maxn; i++) vec[i].clear();
50 for(int i = 1, a, b; i < n; i++) {
51 scanf("%d%d", &a, &b);
52 vec[a].pb(b);
53 vec[b].pb(a);
54 }
55 scanf("%d", &symbol);
56 dfs(1, -1);
57 cout << min(dp[1][0], dp[1][1]) << endl;
58 }
59 return 0;
60 }
61