题目链接:http://poj.org/problem?id=1947
题意:给出一棵n个节点的树,问剖出一颗含有p个节点的子树最少需要砍掉多少条边.(n<= 150)
思路:
树形DP,f[i][j]表示在以i为根的树上剖出j个节点并且包含i节点的子树最少需要砍掉的边数。
初始f[i][1]等于他的孩子树. f[i][j] = min(f[k][l]+f[i][j-l]-1),减1是因为初始我们把他的所有孩子都砍掉了,现在接上他们.
代码:
#include<cstdio>
#include<iostream>
#include<vector>
#include<cstring>
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
const int maxn = 2e5+5;
const double eps = 1e-12;
const int inf = 0x3f3f3f3f;
int n,m;
vector<int> mp[234];
int f[234][234],ve[234];
void dfs(int x,int p)
{
ve[x] = 1;
int k = mp[x].size();
for(int i = 0;i< k;i++)
{
int v = mp[x][i];
if(v == p) continue;
dfs(v,x);
ve[x]+= ve[v];
for(int j = ve[x];j> 1;j--)
{
for(int l = 1;l< j;l++)
{
f[x][j] = min(f[x][j],f[x][l]+f[v][j-l]-1);
}
}
}
return ;
}
int main()
{
mem(f,inf);
cin>>n>>m;
for(int i = 1;i<= n;i++) f[i][1] = 0;
for(int i = 1,x,y;i< n;i++)
{
scanf("%d %d",&x,&y);
mp[x].push_back(y);
mp[y].push_back(x);
f[x][1]++;
}
dfs(1,0);
int ans = f[1][m];
for(int i = 2;i<= n;i++)
ans = min(ans,f[i][m]+1);
cout<<ans<<endl;
return 0;
}