显然考虑 $n^2$ 的树形 $dp$
设 $f[x][i]$ 表示 $x$ 的子树内选了 $i$ 个节点染黑，子树内所有边对整颗树的最大贡献
考虑子树的合并，显然对于 $(u,v),v \in son[u]$ ，设边权为 $w$ ，这条边的贡献可以通过 $v$ 子树内的黑节点数算出
因为确定了子树内的黑节点数就可以算出子树外的黑节点数，子树白节点也可以用子树节点数减去子树黑节点数得到
那么贡献就容易确定
那么对于 $f[u][i]$ ，枚举儿子 $v$ 并枚举 $v$ 内的黑节点数 $j$ ，有转移：
$f[u][i]=max(f[u][i],f[u][i-j]+f[v][j]+wj(K-j)+w(sz[v]-j)(n-sz[v]-K+j))$
注意代码实现的时候 $i$ 要从大到小枚举，并且 $j$ 要先把 $j=0$ 的情况转移好，才能保证 $f[u][i-j]$ 此时不包括 $v$ 的贡献
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> using namespace std; typedef long long ll; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<‘0‘||ch>‘9‘) { if(ch==‘-‘) f=-1; ch=getchar(); } while(ch>=‘0‘&&ch<=‘9‘) { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=2007; int n,m,sz[N]; int fir[N],from[N<<1],to[N<<1],val[N<<1],cntt; inline void add(int a,int b,int c) { from[++cntt]=fir[a]; fir[a]=cntt; to[cntt]=b; val[cntt]=c; } ll f[N][N]; void dfs(int x,int fa) { sz[x]=1; memset(f[x],-1,sizeof(f[x])); f[x][0]=f[x][1]=0; for(int i=fir[x];i;i=from[i]) { int &v=to[i],&w=val[i]; if(v==fa) continue; dfs(v,x); sz[x]+=sz[v]; for(int j=min(sz[x],m);j>=0;j--) for(int k=0;k<=min(sz[v],j);k++)// if(f[x][j-k]>=0&&n-sz[v]>=m-k) f[x][j]=max(f[x][j], f[x][j-k] + f[v][k] + 1ll*w* ( k*(m-k) + (sz[v]-k)*(n-sz[v]-m+k) ) ); } } int main() { n=read(),m=read(); int a,b,c; for(int i=1;i<n;i++) { a=read(),b=read(),c=read(); add(a,b,c),add(b,a,c); } dfs(1,0); printf("%lld\n",f[1][m]); return 0; }
原文：https://www.cnblogs.com/LLTYYC/p/11751670.html