题目简述
一棵 $n$ 个点的树，断掉 $k$ 条边分离出一棵大小为 $p$ 的子树，最小化 $p$
值得注意的是，s建树时两点有父子关系（具体见原题）
思路
设 $f_{i,j}$ 表示以 $i$ 为根的子树中，保留 $j$ 个点所需要断掉的边数（你也可以理解为：以 $i$ 为根的子树断掉 $f_{i,j}$ 条边，使形成的若干子树中以 $i$ 为根的子树大小为 $j$ ）。值得注意的是，这里的 $f_{i,j}$ 是在子树内部需要断掉的边数，若要分离出的子树以 $i$ 为根，还需要断掉 $i$ 与其父亲相连的那条边。
在以 $i$ 为根的子树中断边，如果只断掉 $i$ 与其儿子相连的边，显然有很大局限性，于是我们还要从其儿子的子树中断边 —— 我们可以枚举儿子对 $i$ 的贡献进行转移：
$\large f_{i,j}=\min(f_{i,j},\ f_{i,j-k}+f_{son_{i}，k}-1)$
当我们将 $i$ 的某个儿子拿出来的时候，它与 $i$ 之间的边已经在 $f_{i,j-k}$ 中断开，是一个独立的子问题所以大小为 $j-k$ 的部分和大小为 $k$ 的部分并没有联通，构不成我们想要的大小为 $j$ 的一部分。于是我们只需要将多余断掉的那一条边重新连接，在转移中体现为最后的减一。
最后只需要枚举分离出的大小为 $p$ 的子树的根节点就可以得到答案。与上面所说的道理一样，当分离部分以某个点为根的时候，还需要将它与其父亲断开（如果有父亲的话），代码中体现为对于有父亲的节点最后需要将答案加一。
Code
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<climits>
#define int long long
using namespace std;
const int MaxN = 152;
int n, p, ans = INT_MAX, head[MaxN], degree[MaxN], cntEdge, f[MaxN][MaxN], subtreeSize[MaxN], father[MaxN];
struct Edge{
int destination, nextEdge;
}edge[MaxN*2];
#define thisSon edge[i].destination
inline int Read(){
int num = 0, op = 1;
char ch = getchar();
while(!isdigit(ch)){
if(ch == '-') op = -1;
ch = getchar();
}
while(isdigit(ch)){
num = num * 10 + ch - '0';
ch = getchar();
}
return num * op;
}
inline void AddEdge(int u, int v){
cntEdge++;
edge[cntEdge].destination = v;
edge[cntEdge].nextEdge = head[u];
head[u] = cntEdge;
degree[u]++;
father[v] = u;
return;
}
inline void DP(int x){
subtreeSize[x] = 1;
if(!degree[x]){
f[x][1] = 0;
return;
}
for(int i = head[x]; i; i = edge[i].nextEdge){
DP(thisSon);
subtreeSize[x] += subtreeSize[thisSon];
for(int j = subtreeSize[x]; j>=0; j--)
for(int k=1; k<j; k++)
f[x][j] = min(f[x][j], f[x][j-k] + f[thisSon][k] - 1); // rebuild an edge to connect the j-k-sized part and the k-sized part
}
}
signed main(){
n = Read(), p = Read();
for(int i=1; i<n; i++){
int u = Read(), v = Read();
AddEdge(u, v);
}
memset(f, 0x3f, sizeof(f));
for(int i=1; i<=n; i++)
f[i][1] = degree[i];
DP(1);
for(int i=1; i<=n; i++){
if(father[i]) f[i][p] += 1; // destroy an exrta edge to disconnect i and its father
ans = min(ans, f[i][p]);
}
printf("%lld", ans);
return 0;
}