链接：
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3659
题意：
有n（n≤10000）台机器形成树状结构。要求在其中一些机器上安装服务器，
使得每台不是服务器的计算机恰好和一台服务器计算机相邻。求服务器的最少数量。
分析：
按照每个结点的情况进行分类：
一、d(u,0)：u是服务器，则每个子结点可以是服务器也可以不是。
二、d(u,1)：u不是服务器，但u的父亲是服务器，这意味着u的所有子结点都不是服务器。
三、d(u,2)：u和u的父亲都不是服务器。这意味着u恰好有一个儿子是服务器。
状态转移方程如下（其中v是u的子结点）：
d(u,0) = sum{min(d(v,0), d(v,1))} + 1。
d(u,1) = sum(d(v,2))。
d(u,2)需要枚举当服务器的子结点编号v，然后把其他所有子结点v'的d(v',2)加起来，再和d(v,0)相加。
可以利用已经算出的d(u,1)写出一个新的状态转移方程：d(u,2) = min(d(u,1) – d(v,2) + d(v,0))。
最终答案为min(d(1,0), d(1,2))。
代码：
#include <cstdio>
#include <vector>
using namespace std; const int UP = + ;
int F[UP], d[UP][]; // F[r]为结点r的父结点
vector<int> seq, edge[UP]; // seq为结点访问顺序序列 void dfs(int r, int f){
F[r] = f;
seq.push_back(r);
for(int i = ; i < edge[r].size(); i++){
int b = edge[r][i];
if(b != f) dfs(b, r);
}
} int main(){
int n;
while(scanf("%d", &n) == ){
seq.clear();
for(int i = ; i <= n; i++) edge[i].clear();
for(int f, b, i = ; i < n; i++){
scanf("%d%d", &f, &b);
edge[f].push_back(b);
edge[b].push_back(f);
} dfs(, -); // 以结点1为根建立有根树
for(int p = seq.size() - ; p >= ; p--){
int r = seq[p];
d[r][] = ; d[r][] = ;
for(int i = ; i < edge[r].size(); i++){
int b = edge[r][i];
if(b == F[r]) continue;
d[r][] += min(d[b][], d[b][]); // d[r][0]代表r是服务器
d[r][] += d[b][]; // d[r][1]代表r不是服务器，但其父结点是
}
d[r][] = ; //d[r][2]代表r及其父结点都不是服务器
for(int i = ; i < edge[r].size(); i++){
int b = edge[r][i];
if(b == F[r]) continue;
d[r][] = min(d[r][], d[r][] - d[b][] + d[b][]);
}
}
printf("%d\n", min(d[][], d[][]));
scanf("%d", &n); // 读取结束标记
}
return ;
}