Perfect Service poj3398

3398 -- Perfect Service

题目大意：有n个电脑形成一棵树，其中一些电脑可以作为服务器，问如果要使所有非服务器的电脑都只与一个服务器相邻，最少的服务器数是多少

1<=n<=10000

思路：我们用dp[u][0]表示u是服务器，dp[u][1]表示u不是服务器但父结点是服务器，dp[u][2]表示u不是服务器且父结点也不是服务器。我们从下向上遍历，如果u是服务器，那么子节点可以是服务器也可以不是，dp[u][0]=min(dp[v][0],dp[u][1]);如果u不是服务器，但父节点是服务器，则他的所有子节点都不能是服务器，dp[u][1]+=dp[v][2];如果u不是服务器，且父结点也不是服务器，那么子节点里至少有一个是服务器，需要枚举每个节点是服务器，其他节点不是时的最小值，即dp[u][2]=dp[v其他]+dp[v][0]，但我们已经算出v都不是服务器的情况了，所以我们可以直接用所有子节点都不是服务器的情况减去dp[v][2]，即dp[u][2]=dp[v][1]-dp[v][2]+dp[v][0]

#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
const int N = 1e5 + 5;
int dp[N][3], vis[N];
vector<int>e[N * 2];
int n;
void init()
{
	for (int i = 1; i <= n; i++)
	{
		e[i].clear();
		vis[i] = 0;
	}
}
void dfs(int u)
{
	vis[u] = 1;
	dp[u][0] = 1;
	dp[u][1] = 0;
	dp[u][2] = N;//要求最小值，初始化为最大值
	for (int i = 0; i < e[u].size(); i++)
	{
		int v = e[u][i];
		if (!vis[v])
		{
			dfs(v);
			dp[u][0] += min(dp[v][0], dp[v][1]);
			dp[u][1] += dp[v][2];
			dp[u][2] = min(dp[u][2], dp[v][0] - dp[v][2]);//先对每个点枚举
		}
	}
	dp[u][2] += dp[u][1];//再加上子节点都不是服务器的情况
}
int main()
{
	while (~scanf("%d", &n))
	{
		init();
		for (int i = 1; i <= n - 1; i++)
		{
			int u, v;
			scanf("%d%d", &u, &v);
			e[u].push_back(v);
			e[v].push_back(u);
		}
		int x;
		dfs(1);
		printf("%d\n", min(dp[1][0],dp[1][2]));//根节点的父结点不是服务器
		scanf("%d", &x);
		if (x == -1)
			return 0;
	}
}