View Code of Problem 1032

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define MAXN 200
#define INF 0x3f3f
using namespace std;
vector<int> G[MAXN];
int dp[MAXN][MAXN];//dp[i][j]存储以i节点为根的树 选j个点 最少删的边数
int pre[MAXN];
int N, P;
void init()
{
    for(int i = 1; i <= N; i++)
        G[i].clear(), pre[i] = i;
}
void getMap()
{
    int a, b;
    for(int i = 1; i < N; i++)
    {
        scanf("%d%d", &a, &b);
        G[a].push_back(b);
        pre[b] = a;
    }
}
int num[MAXN];
void DFS(int u)
{
    dp[u][1] = 0;//初始 自己不删边
    for(int i = 0; i < G[u].size(); i++)
    {
        int v = G[u][i];
        DFS(v);
        for(int j = P; j >= 0; j--)
        {
            int t = dp[u][j] + 1;//直接删掉 与 子节点v 相连的边
            for(int k = 0; k <= j; k++)
                t = min(t, dp[u][j-k] + dp[v][k]);
            dp[u][j] = t;
        }
    }
}
void solve()
{
    int root;
    for(int i = 1; i <= N; i++)
    {
        if(pre[i] == i)
        {
            root = i;
            break;
        }
    }
    memset(dp, INF, sizeof(dp));
    DFS(root);
    int ans = INF;
    for(int i = 1; i <= N; i++)
    {
        if(i == root)//删边后 原根节点 依旧在
            ans = min(ans, dp[i][P]);
        else//删边后 原根节点已经没了 加上去掉根的一条边
            ans = min(ans, dp[i][P] + 1);
    }
    printf("%d\n", ans);
}
int main()
{
    while(scanf("%d%d", &N, &P) != EOF)
    {
        init();
        getMap();
        solve();
    }
    return 0;
}