Gym 102222G Factories（贡献+树形dp+01背包）

链接：https://codeforces.com/gym/102222/problem/G

题意：给出一个树，从所有的叶子节点中选出m个节点，使得这m个节点间的 sigma（任意2点间的距离）最小。求最小的sigma。 n<1e5, k<100。

题解：求任意2点间的距离和， 可考虑贡献，考虑每条边对答案的贡献，w*k*(m-k)。对每个子树考虑  dp[u][j]=min(dp[u][j], dp[u][j-k]+dp[v][k]+1ll*w*k*(m-k))，每个子树有siz[v]（多少个叶子节点）的节点可取，考虑01背包，注意V枚举的时候逆序。

#include <bits/stdc++.h>
using namespace std;

const int maxn=1e5+5;
const long long inf=1e17+5;
int n, m;
int head[maxn], degree[maxn], siz[maxn], tot;
struct Edge{
    int to, next, val;
}edge[maxn*2];
long long dp[maxn][105];

void addedge(int u, int v, int w)
{
    edge[++tot].to=v, edge[tot].val=w, edge[tot].next=head[u];
    head[u]=tot;
}

void init_edge()
{
    tot=0;
    memset(head, -1, sizeof(head));
    memset(degree, 0, sizeof(degree));
    memset(siz, 0, sizeof(siz));
}

void init_dp()
{
    for(int i=1; i<=n; i++)
    {
        dp[i][0]=0;
        for(int j=1; j<=m; j++)
            dp[i][j]=inf;
    }
    for(int i=1; i<=n; i++)
        if(degree[i]==1) siz[i]=1, dp[i][1]=0;
}

void dfs(int u, int pre)
{
    for(int i=head[u]; i!=-1; i=edge[i].next)
    {
        int v=edge[i].to, w=edge[i].val;
        if(v==pre) continue;
        dfs(v, u);
        siz[u]+=siz[v];
        for(int j=min(m, siz[u]); j>=1; j--)  //逆序,背包问题, siz[u]个，每个都是选或者不选
            for(int k=1; k<=min(j, siz[v]); k++)
                dp[u][j]=min(dp[u][j], dp[u][j-k]+dp[v][k]+1ll*w*k*(m-k));
    }
}

int main()
{
    ios::sync_with_stdio(false), cin.tie(0);
    //freopen("in.txt", "r", stdin);
    int T, kase=0;
    for(cin>>T; T--; )
    {
        init_edge();
        int rt=1;
        cin>>n>>m;
        for(int u,v,w,i=1; i<n; i++)
        {
            cin>>u>>v>>w;
            addedge(u, v, w), addedge(v, u, w);
            degree[u]++, degree[v]++;
            if(degree[u]>1) rt=u;
            if(degree[v]>1) rt=v;
        }
        init_dp();
        dfs(rt, 0);
        cout<<"Case #"<<++kase<<": "<<dp[rt][m]<<"
";
    }
    return 0;
}