2019银川网络赛G（树形背包的一点优化）

这题一开始有了nkk的dp 然后一看肯定超时啊 但是感觉跑不满 听学长说有一种优化可以降到nk 学了一下不难理解 但是具体的证明可能麻烦一点 具体参考这个博客https://blog.csdn.net/lyd_7_29/article/details/79854245

#include<bits/stdc++.h>

#define ll long long
#define maxn 100010
using namespace std;
int T, n, k, siz[maxn], cas, ru[maxn];
ll ans, f[maxn][110];

struct edge {
    int v, t;

    edge() {}

    edge(int v, int t) : v(v), t(t) {}
};

vector<edge> G[maxn];


void Dfs(int now, int from) {
    if (ru[now] == 1) {
        siz[now] = 1;
        f[now][0] = f[now][1] = 0;
    }
    for (int i = 0; i < G[now].size(); i++) {
        int v = G[now][i].v;
        int t = G[now][i].t;
        if (v == from)continue;
        Dfs(v, now);
        int S = min(k, siz[now]);
        for (int j = S; j >= 0; j--) {
            int T = min(k - j, siz[v]);
            for (int r = 1; r <= T; r++) {
                f[now][j + r] = min(f[now][j + r], f[now][j] + f[v][r] + 1ll * r * (k - r) * t);
            }
        }
        siz[now] += siz[v];
        /*
         另一种稍慢的写法
        int S = min(k, siz[now] + siz[v]);
        for (int j = S; j >= 0; j--) {
            int T = min(j, siz[v]);
            for (int r = max(j - siz[now], 0); r <= T; r++) {
                f[now][j] = min(f[now][j], f[now][j - r] + f[v][r] + 1ll * r * (k - r) * t);
            }
        }
        siz[now] += siz[v];
        */
    }
    ans = min(ans, f[now][k]);
}

int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &k);
        ans = 1e18;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= k; j++)
                f[i][j] = 1e18;
        for (int i = 1; i <= n; i++) {
            G[i].clear();
            siz[i] = 0;
            ru[i] = 0;
        }
        int u, v, t;
        for (int i = 1; i < n; i++) {
            scanf("%d%d%d",&u,&v,&t);
            G[u].push_back(edge(v, t));
            G[v].push_back(edge(u, t));
            ru[u]++;
            ru[v]++;
        }
        int rot = 1;
        for (int i = 1; i <= n; i++) {
            if (ru[i] > 1)rot = i;
        }
        Dfs(rot, 0);
        printf("Case #%d: %lld\n", ++cas, ans);
    }
    return 0;
}