学步园

Problem Address：http://poj.org/problem?id=1947

【前言】

        何谓“树形DP”？简单地说树形DP就是在树上进行的DP。

        按我的理解，”树形DP“应该叫做“树维DP”。这么说，最简单的DP是一维DP，在一个数组上进行。接下去是二维DP，存放在一个二维数组里，其中一维用于表示所有的点，另一维用于表示该点的各种状态。而树形DP更多地像是二维DP，只不过表示所有点的那一维长成一棵树的形状。

        一般地，二维DP用两个循环即可得出答案，而树形DP也是如此。不过，由于树的特殊结构，很多时候并不是直接就可以扫描。在树形DP上用得较多的或许就是所谓的“记忆化搜索”了。

        于是，照葫芦画瓢地完成了第一道树形DP。

【思路】

建树：

        这道题有多种做法，其中一种是把这棵树建成二叉树，即把普通的树转化为左儿子有兄弟的形式。

转移：

       dp[i][j]，表示对于结点i，使其得到结点数为j要去掉的最小边数。每个结点都有两种状态，选与不选。如果不选，则其值为其兄弟结点的值加一（去掉该点与父结点的连边）。如果选，则为其儿子结点与兄弟结点的值的和。

       把每个结点作为根结点并枚举。除了真正意义上的根结点，其他结点枚举的结果都要加上一，表示把其跟其父节点的连边去掉所花费的代价。

【代码】

#include <iostream>
using namespace std;

const int maxn = 150;
const int MAX = 99999999;

int brother[maxn+5];
int son[maxn+5];
int dp[maxn+5][maxn+5];

void init(int n)
{
	int i, j;
	for (i=0; i<=n; i++)
	{
		brother[i] = son[i] = 0;
		for (j=0; j<=n; j++)
		{
			dp[i][j] = MAX;
		}
	}
}

int solve(int v, int j)
{
	int ans, t1, t2, k;
	if (dp[v][j]<MAX)
		return dp[v][j];

	if (v==0 && j==0) return dp[0][0] = 0;
	if (v==0 && j!=0) return dp[0][j] = -1;

	ans = solve(brother[v], j);
	if (ans!=-1) ans++;//不选该结点的值
	else ans = MAX;
	
	for (k=0; k<=j-1; k++)
	{
		t1 = solve(son[v], k);
		t2 = solve(brother[v], j-k-1);
		if (t1>-1 && t2>-1 && t1+t2<ans)
			ans = t1 + t2;//选该结点的值
	}
	
	if (ans==MAX) ans = -1;
	return dp[v][j] = ans;
}

int main()
{
	int n, p;
	int a, b, ans;
	int i, t;
	scanf("%d %d", &n, &p);
	init(n);
	for (i=1; i<n; i++)
	{
		scanf("%d %d", &a, &b);
		brother[b] = son[a];
		son[a] = b;
	}
	ans = solve(son[1], p-1);//单独处理根结点
	for (i=1; i<=n; i++)
	{
		t = solve(son[i], p-1);
		if (t>-1 && t+1<ans)
			ans = t+1;//枚举各结点的结果加一
	}
	printf("%d\n", ans);
	return 0;
}