思路

转移什么按边计算都是套路...
小菜鸡每次接触边界问题就死翘翘啦.
这题的第二维必须枚举,或者你提前算的贡献,因为你一直在想要不要重复的问题,所以你第一维肯定正序,但是注意当你时,本来就已经更新过了,已经不是这个值了,现在你又更新一次,这里就存在重复了.
对于其他也没什么好讲的...我竟然上课理解这个东西,想了半天....
具体做法是:不按点算,按边算贡献.

定义表示到了这个子树,有个点染黑的子树边的最大贡献.
然后转移方程就skip了.

code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e3+5;

struct node{
    ll x,w;
};
vector<node>g[N];
ll f[N][N];//u这个节点的子树选取了k个黑点的最大价值.
ll sz[N],n,k;

void dfs(ll u,ll fa)
{
    sz[u]=1;f[u][0]=f[u][1]=0;
    for(auto v:g[u])
    {
        if(v.x==fa)    continue;
        dfs(v.x,u);
        sz[u]+=sz[v.x];
        for(ll i=min(sz[u],k);i>=0;i--)
        {
            for(ll j=0;j<=min(sz[v.x],i);j++)
            {
                ll val=1ll*(1ll*j*(k-j)+1ll*(sz[v.x]-j)*(n-k-(sz[v.x]-j)))*v.w;//黑+黑,白+白.
                f[u][i]=max(f[u][i],f[u][i-j]+f[v.x][j]+val);
            }
        }
    }
}
//for(ll j=min(sz[v.x],i);j>=0;j--)
//for(ll j=0;j<=min(sz[v.x],i);j++)

int main()
{
    scanf("%lld%lld",&n,&k);
    memset(f,-0x3f,sizeof f);
    for(int i=1;i<n;i++)
    {
        ll fr,to,dis;
        scanf("%lld%lld%lld",&fr,&to,&dis);
        g[fr].push_back({to,dis});
        g[to].push_back({fr,dis});
    }
    dfs(1,1);
    printf("%lld\n",f[1][k]);
    return 0;
}