题解 | #小d和送外卖#

一道典型的树形背包，看到n，k值 m<=50 果断用m做完背包第2维，就是选不选的普遍问题了

dp[i][j]：以节点i为根节点子树中没选j个点情况下的最短路径，相当于用了一个滚动数组优化了一个维度 下面直接上代码，里面有过程注释

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int inf = 0x3f3f3f3f;
const int N = 2e5+8;
typedef long long ll;
int n,m,k,dp[N][60],cnt[N],tmp[60];
vector<int>e[N];
void dfs(int cur,int fa){
    for(int i=0;i<e[cur].size();i++){
        int now = e[cur][i];
        if(now==fa)continue;
        dfs(now,cur);
        cnt[cur]+=cnt[now];
        //dp[i][j][m] 因为是树形dp 相当于自然列举了j个待选项
        //相当于直接用滚动数组优化掉了第2维度 到第j个为止
        //dp[i][j]节点i为根节点子树没选j个点情况下最小路径
        //可以用一个数组巧妙的不断重置来替代滚动数组
        memset(tmp,inf,sizeof(tmp));
        for(int j=0;j<=min(cnt[cur],m);j++){//cur节点子树不选j个时
            for(int k=0;k<=min(cnt[now],j);k++){//当前子节点不选k个时
                tmp[j]=min(tmp[j],dp[cur][j-k]+dp[now][k]+(k==cnt[now]?0:2));
                //若k==cnt[now]就是子树全部放弃不需要再往下走
            }
        }
        memcpy(dp[cur],tmp,sizeof(tmp));
    }
}
signed main()
{
    cin>>n>>m;
    for(int i=1;i<=n-1;i++){
        int u,v;
        cin>>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    cin>>k;
    for(int i=1;i<=k;i++){
        int x;
        cin>>x;
        cnt[x]++;
    }
    dfs(1,0);
    cout<<dp[1][min(m,k)]<<'\n';
    return 0;
}