题意：
思路：
那么，我们考虑一个结点可以被谁染色，不难想出，可以有3种情况：被自己染色，被儿子染色，被父亲染色
我们不妨设：
f[i][0] 代表被自己染色 f[i][1] 代表被父亲染色 f[i][2] 代表被儿子染色
设当前节点是 u ，儿子节点是 v
我们来考虑下转移方程：
这时我们可以想一下，u被自己染色可以由什么转移过来，如果u已经被自己染色了的话，他的儿子v可以选择自己染色，也可以选择被自己的儿子染色，当然也可以被u染色，当然，我们要选最小的，所以转移方程就是
f[u][0] += min(f[v][0],f[v][1],f[v][2] )
如果被父亲结点(fa)染色了，那么u的儿子v只能选择自己染色或者被它的儿子染色，转移方程为
f[u][1] += min(f[v][1],f[v][0] )
这是最麻烦的一种情况，因为u可能有多个儿子，只要有一个儿子自己染色了，就可以将u覆盖，这种情况就成立了
而现在它的儿子有两种情况，分别是自己染色和被它儿子染色
我们可以先假设每个儿子都是被它自己染色（v被自己染色）的，然后看一下u的每个儿子（v）被其儿子染色是否使结果变得更小，把能让结果更小的 自己染色（v自己染色）的儿子 替换为 被其儿子染色的儿子（v被它儿子染色）的儿子
#include <iostream>#include <algorithm>#include <string>#include <string.h>#include <vector>#include <map>#include <stack>#include <set>#include <queue>#include <math.h>#include <cstdio>#include <iomanip>#include <time.h>#include <bitset>#include <cmath>#define LL long long#define INF 0x3f3f3f3f#define ls nod<<1#define rs (nod<<1)+1const double eps = 1e-10;const int maxn = 1e5 + 10;const LL mod = 1e9 + 7;int sgn(double a){return a < -eps ? -1 : a < eps ? 0 : 1;}using namespace std;struct edge { int v,nxt;}e[maxn << 1];int head[maxn];int cnt;int f[maxn][3];inline void add_edge(int u,int v) { e[++cnt].v = v; e[cnt].nxt = head[u]; head[u] = cnt;}void dfs(int u,int fa) { f[u][0] = 1; int tot = 0; int g[maxn]; for (int i = head[u];~i;i = e[i].nxt) { int v = e[i].v; if (v == fa) continue; dfs(v,u); f[u][0] += min(f[v][0],min(f[v][1],f[v][2])); f[u][1] += min(f[v][0],f[v][2]); f[u][2] += f[v][0]; g[++tot] = f[v][2] - f[v][0]; } if (!tot) f[u][2] = INF; else { sort(g+1,g+1+tot); for (int i = 1;i < tot;i++) { if (g[i] < 0) f[u][2] += g[i]; else break; } }}int main() { cnt = 0; memset(head,-1, sizeof(head)); int n; cin >> n; for (int i = 1;i < n;i++) { int u,v; cin >> u >> v; add_edge(u,v); add_edge(v,u); } dfs(1,0); cout << min(f[1][0],f[1][2]) << endl; return 0;}
