补充
样例输入
6
1 3
2 3
3 4
4 5
4 6
0
2
1 2
-1
样例输出
2
1
思路
题目描述了一个树形结构，我们考虑使用树形 (DP) ，由于多了一个限制条件：一个客户端只有一个服务器。
那么我们设置三种状态：
(dp[u][0]) 表示当前节点 (u) 为服务器，孩子是否为服务器均可，
(dp[u][1]) 表示当前节点 (u) 为客户端， (u) 的父亲为服务器， (u) 的儿子均为客户端，
(dp[u][2]) 表示当前节点 (u) 为客户端， (u) 的父亲为客户端， (u) 的其中一个儿子为服务器。
第一个比较容易得到 (dp[u][0] = sum dp[v][1] + 1.)
第二个比较容易得到 (dp[u][1] = sum dp[v][2].)
下面我们分析第三个，容易得到 (dp[u][2] = min (dp[u][2] ,dp[V][0] + sum dp[v][2]).(V != v))
但是时间复杂度过于太高，那么我们考虑进行优化：
可以发现，(sum dp[v][2] = dp[u][1].) ，那么 (sum dp[v][2] + dp[V][0] = dp[u][1] - dp[V][2] + dp[V][0].)
可得状态转移方程： (dp[u][2] = min (dp[u][2] ,dp[u][1] - dp[V][2] + dp[V][0]).)
易错：初始化。
代码
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
using namespace std;
const int MAXN = 1e4 + 10;
struct node {
int next ,to;
}edge[MAXN << 1];
int head[MAXN] ,cnt = 0;
void add (int from ,int to) {
edge[++ cnt].next = head[from];
head[from] = cnt;
edge[cnt].to = to;
return ;
}
int n ,dp[MAXN][3] ,rt;
void dfs (int u ,int fa) {
dp[u][0] = 1 ,dp[u][1] = 0;
dp[u][2] = 10010;
for (int q = head[u];~ q;q = edge[q].next) {
int v = edge[q].to;
if (v == fa) continue;
dfs (v ,u);
dp[u][0] += min (dp[v][0] ,dp[v][1]);
dp[u][1] += dp[v][2];
}
for (int q = head[u];~ q;q = edge[q].next) {
int v = edge[q].to;
if (v == fa) continue;
dp[u][2] = min (dp[u][2] ,dp[u][1] - dp[v][2] + dp[v][0]);
}
return ;
}
void solve () {
rt = 1;
dfs (rt ,0);
printf ("%d
",min (dp[rt][2] ,dp[rt][0]));
return ;
}
int main () {
int cmp ,from ,to;
while (scanf ("%d",&n)) {
memset (head ,-1 ,sizeof (head));
cnt = 0;
for (int q = 1;q < n;++ q) {
scanf ("%d%d",&from ,&to);
add (from ,to) ,add (to ,from);
}
solve ();
scanf ("%d",&cmp);
if (cmp == -1) break;
}
return 0;
}