After solving this problem,I can't help admitting that DP is a world which fully fill with amazement，from the simple one dimension DP,to two dimension DP even to staue DP,tree DP,DP problem is just like a kaleidoscope. But the further reflection reveal that it is always the same because of the similar essence.in my eyes,every DP problem has a (mostly two dimension)table and a equation bewteen two states.If we can controll the table and the relationship between every states,we can conque the problem completely.
The following is my code ,according to the big fish foreverlin.
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
#define INF 999999999
#define MAX 151
vector<int> hash[MAX];
int dp[MAX][MAX];
int n,p;
void dfs(int x)//x代表當(dāng)前訪問結(jié)點(diǎn)
{
int i,j,k;
int len=hash[x].size();
for(i=0;i<len;i++)
dfs(hash[x][i]);
/**///////////////////////////////////////////////////////////////////////////
//后序遍歷，從葉子往上逐層遞推
if(x==1) dp[x][1]=hash[x].size();
else dp[x][1]=hash[x].size()+1;
for(k=0;k<len;k++)
{
for(i=p-1;i>=1;i--)
{
if(dp[x][i]!=INF)
{
for(j=1;i+j<=p;j++)
{
if(dp[hash[x][k]][j]!=INF)
dp[x][i+j]=min(dp[x][i+j],dp[x][i]+dp[hash[x][k]][j]-2);
}
}
}
}
}
int main()
{
scanf("%d%d",&n,&p);
int i,j;
int t1,t2;
for(i=1;i<=n-1;i++)
{
scanf("%d%d",&t1,&t2);
hash[t1].push_back(t2);
}
for(i=1;i<=n;i++)
for(j=1;j<=p;j++)
dp[i][j]=INF;
dfs(1);
int ans=INF;
for(i=1;i<=n;i++)
{
if(dp[i][p]<ans)
ans=dp[i][p];
}
printf("%d\n",ans);
return 0;
}