依赖背包变形——poj1947（经典）

/*
这题显然不适用依赖背包的优化，因为不能保证根是必选的，但是可以按照常规依赖背包的思路进行转移，即每次对一个儿子进行C^2的转移

还是树形的背包，dp[u][j]表示u的子树里，切割出一个大小为j的包含u的联通块的代价
那么dp[u][j]按照常规的依赖背包转移即可
初始状态时dp[u][1],切割掉u的所有儿子的代价
注意本题需要特别讨论u是根和非根的情况，即非根的儿子是度数-1，但是最后以这个点作为中心时就要加上这个减掉的1
*/
#include<bits/stdc++.h>
#include<vector>
using namespace std;
#define N 205
vector<int>G[N];
int dp[N][N],n,p;//dp[u][j]表示u子树下取大小为j的联通块的代价 
void dfs(int u,int pre){
    for(int i=0;i<G[u].size();i++){
        int v=G[u][i];
        if(v==pre)continue;
        dfs(v,u);
        for(int j=p;j>=1;j--)
            for(int k=1;k<j;k++)
                dp[u][j]=min(dp[u][j],dp[v][k]+dp[u][j-k]-1);
    }
}
int main(){
    cin>>n>>p;
    for(int i=1;i<n;i++){
        int u,v;cin>>u>>v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    memset(dp,0x3f,sizeof dp);
    for(int i=1;i<=n;i++)
        dp[i][1]=G[i].size()-1;
    dp[1][1]++;
    
    dfs(1,1);
    int ans=dp[1][p];
    for(int i=2;i<=n;i++)
        ans=min(ans,dp[i][p]+1);
    cout<<ans<<endl;
}