学步园

http://poj.org/problem?id=1947

大意：有n个点组成一个树，问至少要删除多少条边才能获得一棵有p个结点的子树？

分析：树形DP。

思路：用dp[i][j]表示以i为根的子树中留下j个结点的情况下最少需要去除的边数。

因为这里 i 结点的子树不一定只有两棵，直接枚举每个子树剩余结点的分配
的话就相当于枚举了，时间复杂度太高。因此需要在DP中套一层 DP，用F[k][m]
表示i的前k棵子树中，剩余m个结点时的最少去边数。考虑第k棵子树的边去除或是不去除。
（1）、去除k子树：F[k][m] = F[k-1][m] + 1(+1的原因是加上一次去除k子树的边)
（2）、不去除k子树：F[k][m] = min(F[k-1][m-m1] + dp[root[k]][m1]);(k子树剩m1个结点)
综上F[k][m] = min{ F[k-1][m]+1,min{F[k-1][m-m1]+dp[root[k]][m1]} } ;
(求上述状态转移的时候可以用滚动数组优化空间，这里用二维就RE，估计是爆栈了，一直RE)。
滚动数组：F[m] = min{F[m]+1 ,min{F[m-m1]+dp[root[k]][m1]}} ; 
dp[i][j] = F[j]; 最终的答案为，枚举每个结点作为最终树的根，然后得出最小值 ； 

/*
  Name: 	POJ_1947
  Author: 
  Date: 27/09/11 14:03
  Description: 	树形DP 
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

#define MAX 160
#define INF 1000000
#define min(a,b) (a>b?b:a)

using namespace std;

int N,P,edge_num;
struct Node{
	int num,next ;	
}edge[MAX] ;

int g[MAX] ;
bool vis[MAX];
int dp[MAX][MAX];

void add(int a,int b)
{
	++edge_num;
	edge[edge_num].num = b ;
	edge[edge_num].next = g[a] ;
	g[a] = edge_num ;	
}

void dfs(int node)
{
	if(vis[node])	return ;
	vis[node] = true ;	
	int i,j,son_num = 0,num,k,m,m1,min_;
	//int F[MAX];		 
	for(i=1;i<=N;i++)
	{
		dp[node][i] = INF ;			
	}	
	dp[node][0] = 0 ;		//以node为根结点的子树中剩下0个结点最少需要去的边数 
	//进行01背包， 在DP中套DP 
	for(k=1,j=g[node];j!=-1;k++,j=edge[j].next)
	{
		num = edge[j].num ;
		if(!vis[num])
			dfs(num);
		for(m=N;m>0;m--)
		{
			min_ = INF ;
			if(k == 1)
			{
				//F[m] = dp[num][m] ;
				dp[node][m] = dp[num][m-1];		//直接用dp[node][m]作为F[m]的滚动数组； 
				continue ;	
			}		
			else {
				dp[node][m] = dp[node][m] + 1 ;
			//	F[m] = F[m] + 1;	
			}		
			for(m1=0;m1<m;m1++)
			{
				min_ = min(min_,dp[node][m-m1-1]+dp[num][m1]) ;	
			}	
			dp[node][m] = min(min_,dp[node][m]) ;
			
			//F[m] = min(min_,F[m]);
		}
		dp[node][0]++ ;
	}
	/*
	for(i=2;i<=N;i++)
	{
		dp[node][i] = F[i-1];	
	}
	*/	
}

int main()
{
    //freopen("1in.txt","r",stdin);
    //freopen("1out.txt","w",stdout);
    int i,a,b,j;
	while(scanf("%d %d",&N,&P)!=EOF)
	{
		edge_num = 0 ;
		memset(vis,false,sizeof(vis));
		memset(g,-1,sizeof(g));
		for(i=1;i<N;i++)
		{
			scanf("%d %d",&a,&b);
			add(a,b) ;	
		}	
		dfs(1);
		int min_ = dp[1][P-1] ;
		for(j=2;j<=N;j++)		//枚举每个结点作为最后树的根。 
		{
			min_ = min(min_,dp[j][P-1]+1) ;
		}
		printf("%d\n",min_);
		//system("pause");
	}
	
    return 0;
}