这道题还是打一下，毕竟也是一道比较经典的题。
思想值得学习：求点两两之间的距离和不如转化成看一条边会对哪些点对做出贡献。
下面以黑点为例，白点同理。
那么对于一条边（x，y）
根据乘法原理：它对黑点距离的贡献即为y子树内的黑点点数 * y子树外的黑点点数。
于是我们就要对点分配哪些点为黑点，转化为树上背包问题。
然后有一点值得注意，在代码内有注释。
#include<bits/stdc++.h> #define LL long long #define N 2003 using namespace std; int read() { int x=0,f=1;char s=getchar(); while(s<‘0‘||s>‘9‘){if(s==‘-‘)f=-1;s=getchar();} while(s>=‘0‘&&s<=‘9‘){x=x*10+s-‘0‘;s=getchar();} return x*f; } void print(int x) { if(x<0)x=-x,putchar(‘-‘); if(x>9)print(x/10); putchar(x%10+‘0‘); } struct EDGE{ int nextt,to,dis; }w[N*2]; int n,K; int tot=0; int head[N],siz[N]; LL f[N][N]; void add(int a,int b,int c) { tot++; w[tot].nextt=head[a]; w[tot].to=b; w[tot].dis=c; head[a]=tot; } void dfs(int x,int fa) { siz[x]=1;f[x][0]=f[x][1]=0; for(int i=head[x];i;i=w[i].nextt) { int v=w[i].to; if(v==fa)continue; dfs(v,x); siz[x]+=siz[v]; for(int j=min(K,siz[x]);j>=0;--j) { if(f[x][j]!=-1) f[x][j]+=f[v][0]+(LL)siz[v]*(n-K-siz[v])*w[i].dis; //正序转移和倒序转移在本质上并没有差别，但是在这道题中，对于当前枚举的子节点的子树，哪怕一个黑点也没有， //它仍然可以对答案产生贡献，所以我们要先算上这种情况的贡献，否则在接下来的转移中，就会少计算本来就有的价值 for(int k=min(j,siz[v]);k;--k) { if(f[x][j-k]==-1)continue; LL val=(LL)(k*(K-k)+(siz[v]-k)*(n-K-siz[v]+k))*w[i].dis; f[x][j]=max(f[x][j],f[x][j-k]+f[v][k]+val); } } } } int main() { n=read();K=read(); for(int i=1;i<n;++i) { int a=read(),b=read(),c=read(); add(a,b,c);add(b,a,c); } memset(f,-1,sizeof(f)); dfs(1,1); printf("%lld\n",f[1][K]); } /* */
原文：https://www.cnblogs.com/yyys-/p/11844833.html
