【题意】：给出一棵树，然后每个节点都有一个开关控制这个节点的灯，开始的时候树上所有节点的灯都是关闭的。假如这个节点的开关按了一下，那么这个节点和与他相邻的节点的状态都会改变，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 }