【题意】:求树的最小支配集

【题解】:经典树dp题目,求树最小支配集。
               设dp[u][0]表示选择u这个点,且以u为根的子树完全被覆盖的最小个数。
               设dp[u][1]表示u这个点被其儿子覆盖,且以u为根的子树完全被覆盖的最小个数。
               设dp[u][2]表示u这个点被其父亲覆盖,且以u为根的子树完全被覆盖的最小个数。

            然后转移就好明显了。

【代码】:
 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 int n, dp[maxn][3];
24 vector<int> vec[maxn];
25 
26 void dfs(int u, int fa) {
27     dp[u][0] = 1;
28     dp[u][1] = inf;
29     dp[u][2] = 0;
30     int size = vec[u].size();
31     bool isleaf = true;
32     for(int i = 0; i < size; i++) {
33         int v = vec[u][i];
34         if(v == fa) continue;
35         dfs(v, u);
36         isleaf = false;
37         dp[u][0] += min(dp[v][0], dp[v][2]);
38         dp[u][2] += min(dp[v][0], dp[v][1]);
39     }
40     if(!isleaf) {
41         for(int i = 0; i < size; i++) {
42             int v = vec[u][i];
43             if(v == fa) continue;
44             dp[u][1] = min(dp[u][1], dp[u][2] - min(dp[v][0], dp[v][1]) + dp[v][0]);
45         }
46     }
47 }
48 
49 int main() {
50     while(~scanf("%d", &n)) {
51         for(int i = 0; i < maxn; i++) vec[i].clear();
52         for(int i = 1, a, b; i < n; i++) {
53             scanf("%d%d", &a, &b);
54             vec[a].pb(b);
55             vec[b].pb(a);
56         }
57         dfs(1, -1);
58         cout << min(dp[1][0], dp[1][1]) << endl;
59     }
60     return 0;
61 }
62