POJ_1947 Rebuilding Roads--ツリーDP

http://poj.org/problem?id=1947
n個の点が1つの木を構成して、少なくともどれだけの辺を削除して1本のp個の結点の子の木を得ることができますか?
解析:ツリーDP.
構想:iをルートとするサブツリーにj個のノードが残っている場合に最も除去すべき辺数をdp[i][j]で表す.
ここでiノードのサブツリーは必ずしも2本しかないとは限らないので,各サブツリーの残りのノードの割り当てを直接列挙すると列挙に相当し,時間的複雑度が高すぎる.従って、DPにDPを1層装着し、iの前k本の木において、m個のノードが残っている場合の最小エッジ数をF[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-m 1]+dp[root[k]][m 1]);(k子樹残m 1ノード)F[k][m]=min{F[k-1][m]+1,min{F[k-1][m-m 1]+dp[root[k]][m 1]};(上記の状態遷移を求めるときはスクロール配列で空間を最適化することができ、ここでは2次元REで、爆桟と推定され、ずっとRE).スクロール配列:F[m]=min{F[m]+1,min{F[m-m 1]+dp[root[k]][m 1]}}  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
",min_);
		//system("pause");
	}
	
    return 0;
}