题目
题解

Solution

树形DP。
首先不难想到设 f i , j 为以编号为i的节点为根的子树中有j个黑色节点对答案的贡献。
这里发现不好转移，所以把该子树内的点与子树外的点组合所产生的权值也计算进去。考虑统计所有边权对答案的贡献，一条边对答案产生的贡献为边权∗（子树内黑色点数量∗子树外黑色点数量+子树内白色点数量∗子树外白色点数量）。
用 d f s 来求，枚举 i 的每个儿子 j ，现在的 f [ i ] 是包含了 [ 1 , j − 1 ] 子树，然后两重循环枚举范围是 [ 1 , j − 1 ] 的子树总 S i z e 和 j 的 S i z e ，来更新 f [ i ] ，这样更新之后的 f [ i ] 就是 [ 1 , j ] 子树的答案了。
通过奥妙重重的方法可以发现每个点对 ( u , v ) 只会在其 l c a 处被考虑到，所以复杂度是 O ( n 2 ) 。
这种复杂度和51nod1353 树差不多，但不太能理解

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2002;
struct node{
    int to,ne,w;
}e[N<<1];
ll f[N][N],tmp[N];
int sz[N],n,k,i,x,y,tot,h[N],z;
inline char gc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
#define gc getchar
inline int read(){
    int x=0,fl=1;char ch=gc();
    for (;ch<48||ch>57;ch=gc())if(ch=='-')fl=-1;
    for (;48<=ch&&ch<=57;ch=gc())x=(x<<3)+(x<<1)+(ch^48);
    return x*fl;
}
inline void add(int x,int y,int z){
    e[++tot]=(node){y,h[x],z};
    h[x]=tot;
}
inline void dfs(int u,int fa,int pre){
    sz[u]=1;
    for (int i=h[u],v;i;i=e[i].ne)
        if ((v=e[i].to)!=fa){
            dfs(v,u,e[i].w);
            for (int j=0;j<=sz[u] && j<=k;j++) tmp[j]=f[u][j];
            for (int x=0;x<=sz[u] && x<=k;x++)
                for (int y=0;y<=sz[v] && x+y<=k;y++) f[u][x+y]=max(f[u][x+y],tmp[x]+f[v][y]);
            sz[u]+=sz[v];
        }
    for (int i=0;i<=sz[u] && i<=k;i++) f[u][i]+=pre*((ll)i*(k-i)+(ll)(sz[u]-i)*(n-k-(sz[u]-i)));
}
int main(){
    n=read();k=read();
    if (k*2>n) k=n-k;
    for (i=1;i<n;i++) x=read(),y=read(),z=read(),add(x,y,z),add(y,x,z);
    dfs(1,0,0);
    printf("%lld",f[1][k]);
}