题意：
一棵 n 个点的无权树，求最?点覆盖
思路：
那么，我们考虑一个结点可以被谁染色，不难想出，可以有3种情况：被自己染色，被儿子染色，被父亲染色
我们不妨设：
f[i][0] 代表被自己染色 f[i][1] 代表被父亲染色 f[i][2] 代表被儿子染色
设当前节点是 u ，儿子节点是 v
我们来考虑下转移方程：
1自己被自己染色
这时我们可以想一下，u被自己染色可以由什么转移过来，如果u已经被自己染色了的话，他的儿子v可以选择自己染色，也可以选择被自己的儿子染色，当然也可以被u染色，当然，我们要选最小的，所以转移方程就是
f[u][0] += min(f[v][0],f[v][1],f[v][2] )
2被自己的父亲结点染色
如果被父亲结点(fa)染色了，那么u的儿子v只能选择自己染色或者被它的儿子染色，转移方程为
f[u][1] += min(f[v][1],f[v][0] )
3被自己的儿子结点染色
这是最麻烦的一种情况，因为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)+1 const 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; }