【題意】：給出一棵樹，每個(gè)節(jié)點(diǎn)代表一臺(tái)電腦，現(xiàn)在需要選擇一些電腦作為服務(wù)器。如果一臺(tái)電腦被選作服務(wù)器，那么它和和它相鄰的電腦都會(huì)被激活，非服務(wù)器的電腦不能同時(shí)被多臺(tái)服務(wù)器激活。問(wèn)最少要選多少臺(tái)電腦作為服務(wù)器使得所有電腦被激活。
【題解】：樹dp，樹的最小支配集變形。
設(shè)狀態(tài)
dp[u][0] 以u(píng)為根且u為服務(wù)器且整棵子樹都被激活的最小代價(jià)。
dp[u][1] 以u(píng)為根且u被某個(gè)兒子結(jié)點(diǎn)激活且整棵子樹都被激活的最小代價(jià)。
dp[u][2] 以u(píng)為根且u被父親結(jié)點(diǎn)激活且整棵子樹都被激活的最小代價(jià)。
轉(zhuǎn)移 (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];
任取一個(gè)結(jié)點(diǎn)為root進(jìn)行樹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