有一棵点数为N的树，树边有边权。
给你一个在0~N之内的正整数K，你要在这棵树中选择K个点，将其染成黑色，并将其他的N-K个点染成白色。
将所有点染色后，你会获得黑点两两之间的距离加上白点两两之间距离的和的收益。
问收益最大值是多少。
这个题看到受益和最大，还是树上的，立马想到树形 DP。
然后想到树形 DP 本蒟蒻就不会了。。。
以下抄自题解：
设 dp[ u ][ i ] 表示以 u 为根的子树中，选择 i 个黑节点，对答案有多少贡献。
为什么说“对答案有多少贡献”呢？
主要是想到一点：分别考虑每条边对答案的贡献。
即：边一侧的黑节点数×另一侧的黑节点数×边权+一侧的白节点数×另一侧的白节点数×边权。
这点很容易证明，但是不容易想到（原因是我太弱了）。
然后情况就明了了，整个问题成了一个树形背包，考虑每个子节点分配多少个黑色节点（体积），然后算出这条边对答案的贡献（价值）。
这里再一次强调“贡献”，是因为这个贡献不只是在当前子树内，而是对于整棵树来说的。
转移方程长这样：dp[ u ][ i ] = max( dp[ u ][ i ] , dp[ u ][ i - j ] + dp[ v ][ j ] + val )
其中 v 为 u 的子节点， j 为在这个子节点中选择的黑色点的个数， val 为这条边的贡献：val = j×( k - j )×w + ( size[ v ] - j )×( n - m + j - size[ v ] )×w
其中 w 为这条边的边权， n 为总的节点数， m 为总的需要选择的黑色节点数， size[v] 为以 v 为根的子树的节点数量。
附代码：
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define MAXN 2010
using namespace std;
int n,m,c=1;
int head[MAXN],fa[MAXN],size[MAXN];
long long dp[MAXN][MAXN];
struct Tree{
int next,to,w;
}a[MAXN<<1];
inline int read(){
int date=0,w=1;char c=0;
while(c<‘0‘||c>‘9‘){if(c==‘-‘)w=-1;c=getchar();}
while(c>=‘0‘&&c<=‘9‘){date=date*10+c-‘0‘;c=getchar();}
return date*w;
}
inline void add(int u,int v,int w){
a[c].to=v;a[c].w=w;a[c].next=head[u];head[u]=c++;
a[c].to=u;a[c].w=w;a[c].next=head[v];head[v]=c++;
}
void dfs(int rt){
size[rt]=1;
dp[rt][0]=dp[rt][1]=0;
for(int i=head[rt];i;i=a[i].next){
int will=a[i].to;
if(will!=fa[rt]){
fa[will]=rt;
dfs(will);
size[rt]+=size[will];
}
}
for(int i=head[rt];i;i=a[i].next){
int will=a[i].to;
if(will==fa[rt])continue;
for(int j=min(m,size[rt]);j>=0;j--)
for(int k=0;k<=min(size[will],j);k++)
if(dp[rt][j-k]!=-1){
long long val=(long long)(k*(m-k)+(size[will]-k)*(n-size[will]-(m-k)))*a[i].w;
dp[rt][j]=max(dp[rt][j],dp[rt][j-k]+dp[will][k]+val);
}
}
}
void work(){
dfs(1);
printf("%lld\n",dp[1][m]);
}
void init(){
int u,v,w;
n=read();m=read();
m=min(m,n-m);
for(int i=1;i<n;i++){
u=read();v=read();w=read();
add(u,v,w);
}
memset(dp,-1,sizeof(dp));
}
int main(){
init();
work();
return 0;
}
原文：https://www.cnblogs.com/Yangrui-Blog/p/9392519.html