Link

按点来算贡献的话并不好算。考虑到路径长度和可以拆分成每条边的长度乘上其被经过的次数，所以统计边的贡献就可以了。树上一条边会将树分成两边，而该边被经过的次数实质上就是两边的白点个数之积加上黑点个数积。因为定了根，所以其中一边可以按子树考虑，于是就转换成了树形dp。

#include<stdio.h>
#define ll long long
#define N 2007

struct E{
    int next,to;
    ll dis;
}e[N<<1];
int head[N],cnt=0,n,m;
ll dp[N][N],sz[N];

inline void add(int id,int to,ll dis){
    e[++cnt]=(E){head[id],to,dis};
    head[id]=cnt;
}

inline int min(int x,int y){return x<y? x:y;}
inline ll max(ll x,ll y){return x>y? x:y;}
void dfs(int u,int fa){
    sz[u]=1;
    for(int i=head[u];i;i=e[i].next){
        int v=e[i].to;
        if(v==fa) continue;
        dfs(v,u);
        for(int j=sz[u];~j;j--)
            for(int k=sz[v];~k;k--)
                dp[u][j+k]=max(dp[u][j+k],dp[u][j]+dp[v][k]+e[i].dis*(1LL*k*(m-k)+1LL*(sz[v]-k)*(n-m-sz[v]+k)));
        sz[u]+=sz[v];
    }
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<n;i++){
        int u,v; ll dis;
        scanf("%d%d%lld",&u,&v,&dis);
        add(u,v,dis),add(v,u,dis);
    }
    dfs(1,0);
    printf("%lld",dp[1][m]);
}