1. 题目描述
某树形网络由$n, n \in [1, 10^4]$台计算机组成。现从中选择一些计算机作为服务器，使得每当普通计算机恰好与一台服务器连接（并且不超过一台）。求需要指定服务器的最少数量
2. 基本思路
这显然是一个求最优解的问题，并且该网络拓扑结构为树形。因此，考虑树形DP。关键是考虑有哪些状态？不妨令
（1） $dp[u][0]$表示$u$作为服务器，那么它的儿子结点可以是服务器或者普通机；
（2） $dp[u][1]$表示$u$是普通计算机，但是$fa[u]$作为服务器，那么它的儿子结点一定是普通机；
（3） $dp[u][2]$表示$u$和$fa[u]$都是普通计算机，那么它的其中一个儿子结点是服务器。
因此，很容易推导状态转移。
\begin{align}
dp[u][0] &= 1 + \sum \min (dp[v][0], dp[v][1]) \\
dp[u][1] &= \sum dp[v][2] \\
dp[u][2] &= \min (dp[v][0] - dp[v][2]) + \sum dp[v][2] \notag \\
&= \min (dp[v][0] - dp[v][2]) + dp[u][1]
\end{align}
这里注意所求解是$\min (dp[rt][0], dp[rt][2])$，因为根节点没有父亲节点。这是树形DP中很经典的模型。
3. 代码
/* 3398 */
#include <iostream>
#include <sstream>
#include <string>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <deque>
#include <bitset>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <climits>
#include <cctype>
#include <cassert>
#include <functional>
#include <iterator>
#include <iomanip>
using namespace std;
//#pragma comment(linker,"/STACK:102400000,1024000") #define sti set<int>
#define stpii set<pair<int, int> >
#define mpii map<int,int>
#define vi vector<int>
#define pii pair<int,int>
#define vpii vector<pair<int,int> >
#define rep(i, a, n) for (int i=a;i<n;++i)
#define per(i, a, n) for (int i=n-1;i>=a;--i)
#define clr clear
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define lson l, mid, rt<<1
#define rson mid+1, r, rt<<1|1
#define INF 0x3f3f3f3f
#define mset(a, val) memset(a, (val), sizeof(a)) typedef struct {
int v, nxt;
} edge_t; const int maxv = ;
const int inf = 1e5;
const int maxe = maxv * ;
int head[maxv], l;
edge_t E[maxe];
int dp[maxv][];
int n; void init() {
memset(head, -, sizeof(head));
l = ;
} inline void addEdge(int u, int v) {
E[l].v = v;
E[l].nxt = head[u];
head[u] = l++; E[l].v = u;
E[l].nxt = head[v];
head[v] = l++;
} void dfs(int u, int fa) {
int k; dp[u][] = ;
dp[u][] = ;
dp[u][] = inf;
for (k=head[u]; k!=-; k=E[k].nxt) {
int& v = E[k].v;
if (v == fa)
continue;
dfs(v, u);
dp[u][] += min(dp[v][], dp[v][]);
dp[u][] += dp[v][];
dp[u][] = min(dp[u][], dp[v][]-dp[v][]);
} dp[u][] += dp[u][];
} void solve() {
dfs(, );
int ans = min(dp[][], dp[][]);
printf("%d\n", ans);
} int main() {
ios::sync_with_stdio(false);
#ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif int u, v; while (scanf("%d",&n)!=EOF && n) {
init();
rep(i, , n) {
scanf("%d%d",&u,&v);
addEdge(u, v);
}
solve();
scanf("%d", &n);
if (n == -)
break;
} #ifndef ONLINE_JUDGE
printf("time = %ldms.\n", clock());
#endif return ;
}