UVA - 1218 Perfect Service （树形DP）

       思路：dp[i][0]表示i是服务器；dp[i][1]表示i不是服务器，但它的父节点是服务器；dp[i][2]表示i和他的父亲都不是服务器。

      转移方程：

d[u][0] += min(d[v][0], d[v][1]);d[u][1] += d[v][2]; for(int i = 0; i < n; ++i) {      int v= son[u][i];      if(v == PRe) continue;      d[u][2] = min(d[u][2], d[u][1] - d[v][2] + d[v][0]);   }AC代码：
#include<cstdio>#include<algorithm>#include<cstring>#include<utility>#include<string>#include<iostream>#include<map>#include<set>#include<vector>#include<queue>#include<stack>using namespace std;#define eps 1e-10#define inf 0x3f3f3f3f#define PI pair<int, int> const int maxn = 10000 + 5;vector<int>son[maxn];int d[maxn][3];void dfs(int u, int pre) {	d[u][0] = 1;	d[u][1] = 0;	int n = son[u].size();	for(int i = 0; i < n; ++i) {		int v = son[u][i];		if(v == pre) continue;		dfs(v, u);		d[u][0] += min(d[v][0], d[v][1]);		d[u][1] += d[v][2]; 		if(d[u][0] > inf) d[u][0] = inf;		if(d[u][1] > inf) d[u][1] = inf;	} 	d[u][2] = inf;	for(int i = 0; i < n; ++i) {		int v= son[u][i];		if(v == pre) continue;		d[u][2] = min(d[u][2], d[u][1] - d[v][2] + d[v][0]);	}}int main() {	int END, n;	while(scanf("%d", &n) == 1 && n != -1) {		for(int i = 0; i <= n; ++i) son[i].clear();		int x, y;		for(int i = 1; i < n; ++i) {			scanf("%d%d", &x, &y);			son[x-1].push_back(y-1);			son[y-1].push_back(x-1);		}		dfs(0, -1);		printf("%d/n", min(d[0][0], d[0][2]));		scanf("%d", &END);		if(END == -1) break;	}	return 0;}如有不当之处欢迎指出！