【題意】：給出一棵樹，然后每個節點都有一個開關控制這個節點的燈，開始的時候樹上所有節點的燈都是關閉的。假如這個節點的開關按了一下，那么這個節點和與他相鄰的節點的狀態都會改變，on就變off，off變on，求按最少的開關，使所有節點的燈都亮起來。

【題解】：一個樹dp題目，之前想了很久，今天下定決心認真推一次，終于給我推出來了。
               設狀態dp[u][0]表示按下了u這個點的開關，u及其后代的節點都亮了。
                        dp[u][1]表示不按u這個點的開關，u及其后代的節點都亮了。
                        dp[u][2]表示不按u這個點的開關，u不亮，其后代的節點都亮了。

               顯然有：
                        dp[u][0] = ∑dp[v][2] + 1;
                        dp[u][1] = min(奇數個dp[v][0] + 剩下都是dp[v][1]);
                        dp[u][2] = min(偶數個dp[v][0] + 剩下都是dp[v][1]);
                                                                  [其中 v 為 u 的兒子]

                最后，ans = min(dp[1][0], dp[1][1]);

【代碼】：
 1 #include "iostream"
 2 #include "cstdio"
 3 #include "cstring"
 4 #include "algorithm"
 5 #include "vector"
 6 #include "queue"
 7 using namespace std;
 8 #define pb push_back
 9 #define maxn 105
10 const int inf = 1 << 25;
11 int n;
12 vector<int> g[maxn];
13 int dp[maxn][3];
14 
15 void dfs(int u, int fa) {
16     dp[u][0] = 1, dp[u][1] = inf, dp[u][2] = 0;
17     int size = g[u].size();
18     for(int i = 0; i < size; i++) {
19         int v = g[u][i];
20         if(v == fa) continue;
21         dfs(v, u);
22         int odd = dp[u][1], even = dp[u][2];
23         dp[u][0] += dp[v][2];
24         dp[u][1] = min(even + dp[v][0], odd + dp[v][1]);
25         dp[u][2] = min(odd + dp[v][0], even + dp[v][1]);
26     }
27 }
28 
29 int main() {
30     int u, v;
31     while(~scanf("%d", &n) && n) {
32         for(int i = 0; i < maxn; i++) g[i].clear();
33         for(int i = 0; i < n - 1; i++) {
34             scanf("%d%d", &u, &v);
35             g[u].pb(v);
36             g[v].pb(u);
37         }
38         dfs(1, -1);
39         printf("%d\n", min(dp[1][0], dp[1][1]));
40     }
41     return 0;
42 }