原题链接:UVA1218 完美的服务 Perfect Service

题目大意

给定一个\(n\)个点的无向树,现要在某些点上设立服务器.每个不是服务器的点必须只恰好跟一个是服务器的点相连.问最少要放置几个服务器.

数据范围
\(1 \leq n \leq 10000\)

注意正无穷不要设置0x3f3f3f3f,据说有类似菊花图爆数据的.

思路

这是一个比较明显而且套路的树形DP的模型.先划分一下状态,这个题的限制条件是一个不是服务器的点只能和一个服务器连接,服务器之间连几个无所谓.那么比较容易想到这样的划分:\(f[u][j]\)表示以\(u\)为根的子树里,\(j=0\)为\(u\)是服务器,他的儿子是不是无所谓;\(j=1\)为\(u\)不是服务器,但是\(u\)的父节点是服务器,那么他的儿子必然不可能是服务器;\(j=2\)表示\(u\)和他父节点都不是服务器,但是如果他不存在父节点,那就不管,那么\(u\)只有一个儿子是服务器.

这里一定要注意是如果有父节点才会要求他不是一个服务器,如果他没有父节点,但是本身也不是服务器,那么其实也是满足定义的.而\(f[u][1]\)是强调有父节点,且必须是服务器的,不然会和状态矛盾.

入口:\(f[u][0] = 1\)是因为要设置自己是服务器.\(f[u][1]=0\)和\(f[u][2]=正无穷\)跟实际状态转移有关.
转移:
①\(f[u][0]\)
因为如果\(u\)是一个服务器,那么\(u\)的儿子是不是服务器是无所谓的,所以直接取较小的就可以了.\(f[u][0] = \sum\limits_{v\in subtree(u)} min(f[v][0],f[v][1]) + 1\).这里的\(1\)一开始就加了,代码里可以不写.
②\(f[u][1]\)
这个时候由于\(u\)不是服务器,但是他的父节点是,又因为每个不是服务器的点只能和一个服务器相连,所以他的儿子\(v\)都不能是服务器,也就是说,对于儿子此时的状态其实就是\(f[v][2]\),自己不能选,父节点\(u\)也不能选,直接拿来用就可以了.\(f[u][1] = \sum\limits_{v\in subtree(u)} f[v][2]\)
③\(f[u][2]\)
这个状态的计算看起来就很奇怪,如果从定义出发的话计算会成平方级,也就是跟儿子的个数的平方级有关的复杂度.显然是不行的,考虑从现有的状态里直接计算出这个状态:因为现在是只有一个\(v\)可以用,所以不妨先把所有的\(f[v][2]\)加起来,然后在里面随便抠一个\(v\),把他变成服务器的代价算出来,实际上就是加一个\(f[v][0]\)再减去一个\(f[v][1]\).因为你要把一开始所有都没选上的状态里那个\(f[v][2]\)给去掉,再加上他作为服务器往下的代价.而且联系前面的内容,由于\(f[u][1]=\sum\limits_{v\in subtree(u)} f[v][2]\)所以这里的表达是可以推出来是\(f[u][2] = {min}_{v\in subtree(u)}(f[u][1] - f[v][2] - f[v][0])\)
出口:答案一共有两种,一种是\(f[root][0]\),一种是\(f[root][2]\),其中根root可以任选,两种取最小值就可以了.没有\(f[root][1]\)的原因是这种情况其实并不合法,因为对于这个\(root\)来说他的形态应该是没有父节点的.

代码

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 10005,M = 2 * N;
int edge[M],succ[M],ver[N],idx;
int n,f[N][3];
void add(int u,int v)
{
	edge[idx] = v;
	succ[idx] = ver[u];
	ver[u] = idx++;
}
void dfs(int u,int fa)
{
	f[u][0] = 1;f[u][2] = 10010;f[u][1] = 0;
	for(int i = ver[u];~i;i = succ[i])
	{
		int v = edge[i];
		if(v == fa)	continue;
		dfs(v,u);
		f[u][0] += min(f[v][0],f[v][1]);
		f[u][1] += f[v][2];
	}
	for(int i = ver[u];~i;i = succ[i])
	{
		int v = edge[i];
		if(v == fa)	continue;
		f[u][2] = min(f[u][2],f[u][1] + f[v][0] - f[v][2]);
	}
}
int main()
{
	while(scanf("%d",&n) == 1)
	{
		memset(ver,-1,sizeof ver);idx = 0;
		if(n == 0)	scanf("%d",&n);
		if(n == -1)	break;
		for(int i = 1;i < n;++i)
		{
			int u,v;scanf("%d%d",&u,&v);
			add(u,v),add(v,u);
		}
		dfs(1,-1);
		printf("%d\n",min(f[1][0],f[1][2]));
	}
    return 0;
}