【題意】：給出一棵樹，每個節點代表一臺電腦，現在需要選擇一些電腦作為服務器。如果一臺電腦被選作服務器，那么它和和它相鄰的電腦都會被激活，非服務器的電腦不能同時被多臺服務器激活。問最少要選多少臺電腦作為服務器使得所有電腦被激活。
【題解】：樹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