总体思路是这样的： 题目链接 有没有大佬看一下思路或者代码有没有问题 （过了样例）（只过了样例）

//*
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2200;
#define int long long
int n, k, weights[MAXN][MAXN];
vector<int> children[MAXN];
int father[MAXN], sib[MAXN], size_sz[MAXN];

void addedge(int a, int b, int w) {
    children[a].push_back(b);
    children[b].push_back(a);
    weights[a][b] = weights[b][a] = w;
}
void read() {
    cin >> n >> k;
    int u, v, w;
    for (int i = 1; i < n; i++) {
        cin >> u >> v >> w;
        addedge(u, v, w);
    }
}
void preproc(int node) {
    int sz = 1;
    int lastchild = 0;
    for (int child : children[node]) {
        if (child != father[node]) {
            father[child] = node;
            if (lastchild)sib[lastchild] = child;
            lastchild = child;
            preproc(child);
            sz += size_sz[child];
        }
    }
    size_sz[node] = sz;
}
inline int c(int p, int s, int w) {
    int val = (p * (k - p) + (s - p) * (n - s - k + p)) * w;
    return val;
}
int f[MAXN][MAXN];
int g[MAXN][MAXN];
inline void calc(int node) {
    for (int child : children[node]) {
        if (child != father[node])calc(child);
    }
    //printf("calc %d\n", node);
    if (!children[node].empty()) {
        int last = children[node].size() - 1;
        int maxp = 0;
        for (int s = last; s >= 0; s--) {
            maxp += size_sz[children[node][s]];
            for (int p = 0; p <= maxp; p++) {
                for (int i = 0; i < p; i++) {
                    g[children[node][s]][p] = max(
                        g[children[node][s]][p],
                        f[children[node][s]][i] + g[sib[children[node][s]]][p - i]
                    );
                }
            }
        }
    }
    for (int p = max(k-(n- size_sz[node]),0LL); p <= size_sz[node]; p++) {
        int w = c(p, size_sz[node], weights[node][father[node]]);
        //printf("calc basic value of f[%d][%d]=%d %d:w %d of p %d\n", node, p, w, node, w, p);
        f[node][p] = w;
        if (!children[node].empty()) {
            int sb = max(g[children[node][0]][p], g[children[node][0]][p - 1]);
            //printf("calc additional value of f[%d][%d]+=%d\n", node, p, sb);
            f[node][p] += sb;
        }
    }
}
int width = 9;
inline void print_f(int f[MAXN][MAXN]) {
    cout << setw(width) << "i\\j";
    for (int i = 0; i <= k; i++) {
        cout << setw(width) << i;
    }
    cout << endl;
    for (int i = 1; i <= n; i++)
    {
        cout << setw(width) << i;
        for (int j = 0; j <= k; j++) {
            cout << setw(width) << f[i][j];
        }
        cout << endl;
    }
}
signed main() {
    read();
    father[1] = 1;
    preproc(1);
    calc(1);
    /*printf("f\n");
    print_f(f);
    printf("g\n");
    print_f(g);*/
    cout << f[1][k];
}
//*/


/*
//by Judge
#include<cstdio>
#include<cctype>
#define ll long long
#define rint register int
#define max(a,b) ((a)>(b)?(a):(b))
using namespace std;
const int M = 2100;
inline ll read() {
    ll x = 0, f = 1; char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') f = -1;
    for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
    return x * f;
}
int n, k, pat;
int head[M];
ll siz[M], dp[M][M], tmp;
struct Edge 
{
    Edge(int a,int b,ll c):to(a),next(b),val(c){}
    Edge(){}
    int to, next; ll val;
}e[M << 1];
inline void add(rint u, rint v, rint c) { e[++pat] = Edge(v,head[u],c), head[u] = pat; }
void dfs(rint u) {
    siz[u] = 1;
    for (rint i = head[u]; i; i = e[i].next) {
        rint v = e[i].to; if (siz[v]) continue;
        dfs(v); ll c = e[i].val;
        for (rint a = siz[u]; a >= 0; --a)  //枚举当前点的以及当前点的其他子树的染色点数 (反向枚举,避免后效性) 
            for (rint b = siz[v]; b >= 0; --b)  //枚举目前处理的子树的染色点数 
                tmp = dp[u][a] + dp[v][b] + c * b * (k - b) + c * (n - k + b - siz[v]) * (siz[v] - b), dp[u][a + b] = max(dp[u][a + b], tmp);
        // dp[u][a] 其他子树内的点各自独立于当前子树内的点的贡献 
        //dp[v][b] 当前子树内的点各自独立于其他子树内的点的贡献 
        //c*b*(k-b) 当前边对连接当前子树内的染色点与子树外的染色点的贡献
        //c*(n-k+b-siz[v])*(siz[v]-b) 当前边对连接当前子树内的未染色点与子树外的未染色点的贡献 
        siz[u] += siz[v];
    }
}
int main() {   //主函数里尽是朴素操作
    n = read(), k = read();
    for (rint i = 1; i < n; ++i) {
        rint x = read(), y = read(); ll c = read();
        add(x, y, c), add(y, x, c);
    }
    dfs(1), printf("%lld\n", dp[1][k]);
    return 0;
}
//*/