推薦此題。基礎(chǔ)樹(shù)型DP。
f[x][i](1 <= i <= p)表示以x為根的子樹(shù)，變成剩下i個(gè)點(diǎn)的子樹(shù)，且剩余子樹(shù)包含根結(jié)點(diǎn)，需要去掉的最少邊數(shù)。
那么父結(jié)點(diǎn)的f值可以由它所有的兒子的f值做背包得到。
最后的答案是min(min(f[i][p]) + 1 (2 <= i <= n), f[1][p])
/**//*************************************************************************
Author: WHU_GCC
Created Time: 2007-8-31 12:40:35
File Name: pku1947.cpp
Description:
************************************************************************/
#include <iostream>
#include <vector>
using namespace std;
#define out(x) (cout << #x << ": " << x << endl)
const int maxint = 0x7FFFFFFF;
typedef long long int64;
const int64 maxint64 = 0x7FFFFFFFFFFFFFFFLL;
template <class T> void show(T a, int n) 
{for (int i = 0; i < n; ++i) cout << a[i] << ' '; cout << endl; }
template <class T> void show(T a, int r, int l) {for (int i = 0; i < r; ++i) show(a[i], l); cout << endl; }
const int maxn = 160;
const int inf = 10000;
int n, p;
vector <int> v[maxn];
int f[maxn][maxn];
void dfs(int now)
{
for (int i = 0; i < v[now].size(); i++)
dfs(v[now][i]);
f[now][1] = v[now].size();
for (int i = 0; i < v[now].size(); i++)
for (int k = p - 1; k >= 0; k--) if (f[now][k] < inf)
{
for (int j = 1; j < p; j++) if (f[v[now][i]][j] < inf)
f[now][k + j] <?= f[now][k] + f[v[now][i]][j] - 1;
}
}
int dp()
{
for (int i = 1; i <= n; i++)
for (int j = 0; j <= n; j++)
f[i][j] = inf;
dfs(1);
int ret = inf;
for (int i = 2; i <= n; i++)
ret <?= f[i][p] + 1;
ret <?= f[1][p];
return ret;
}
int main()
{
while (scanf("%d%d", &n, &p) != EOF)
{
for (int i = 1; i <= n; i++) v[i].clear();
for (int i = 0; i < n - 1; i++)
{
int t1, t2;
scanf("%d%d", &t1, &t2);
v[t1].push_back(t2);
}
printf("%d\n", dp());
}
return 0;
}