题目链接

题意：

在一颗以1为根的树上，最少要删去多少条边才能分离出一颗大小为P的子树

题解：

树上背包

#include<iostream>
#include<sstream>
#include<string>
#include<queue>
#include<map>
#include<unordered_map>
#include<set>
#include<vector>
#include<stack>
#include <utility>
#include<list>
#include<bitset>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<iomanip>
#include<time.h>
#include<random>
using namespace std;
#include<ext/pb_ds/priority_queue.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
using namespace __gnu_pbds;
#include<ext/rope>
using namespace __gnu_cxx;

#define int long long
#define PI acos(-1.0)
#define eps 1e-9
#define lowbit(a) ((a)&-(a))

const int mod = 1e9+7;
int qpow(int a,int b){
	int ans=1;
	while(b){
		if(b&1)ans=(ans*a)%mod;
		a=(a*a)%mod;
		b>>=1;
	}
	return ans;
}
const int INF = 0x3f3f3f3f;
const int N = 1e6+10;
vector<int>g[200];
int sz[200],out[200],f[200][200];
void dfs(int u){
	sz[u]=1;
	for(auto v:g[u]){
		dfs(v);
		sz[u]+=sz[v];
		for(int i=sz[u];i>=1;i--)
			for(int j=1;j<i;j++)
				f[u][i]=min(f[u][i],f[u][i-j]+f[v][j]-1);
	}
}
#define endl '\n'
signed main(){
	std::ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	memset(f,0x3f,sizeof f);
	int n,p; cin>>n>>p;
	for(int i=1;i<n;i++){
		int u,v; cin>>u>>v;
		g[u].push_back(v);
		out[u]++;
	}
	for(int i=1;i<=n;i++)f[i][1]=out[i];
	dfs(1);
	int ans=f[1][p];
	for(int i=1;i<=n;i++)ans=min(ans,f[i][p]+1);
	cout<<ans<<endl;
}