题目概述

有一棵点数为 $n$ 的树，树边有边权。给你一个正整数 $K$ ，你要在这棵树中选择 $K$ 个点，将其染成黑色，并将其他的 $n−K$ 个点染成白色。将所有点染色后，你会获得黑点两两之间的距离加上白点两两之间距离的和的收益。问收益最大值是多少。

解题报告

我快要废了，什么题目都做不来了。这道题如果考虑点之间的收益是很难处理的，但是你如果考虑每条边的收益的话，就是SB题了。$f[i][j]$ 表示 $i$ 的子树中选了 $j$ 个黑点的最优解，然后你只需要树形背包就行了。

我快要废了，树形背包都打不来了。要注意循环的正向和反向以及数组的初值问题。

示例程序

我快要废了，复杂度都分析不来了。DP过程看起来是 $O(n^3)$ 的，但实际上你可以认为你枚举了所有的点对，所以是 $O(n^2)$ 的。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=2000;

int n,K,si[maxn+5];LL f[maxn+5][maxn+5];
int E,lnk[maxn+5],son[(maxn<<1)+5],nxt[(maxn<<1)+5],w[(maxn<<1)+5];

#define Add(x,y,z) son[++E]=(y),w[E]=(z),nxt[E]=lnk[x],lnk[x]=E
#define val(i) ((LL)(i)*(K-(i))*w[j]+(LL)(si[u]-(i))*(n-K-si[u]+(i))*w[j])
void DP(int x,int pre=0){
    for (int j=(si[x]=1,lnk[x]),u;j;j=nxt[j])
        if ((u=son[j])!=pre){
            for (int i=(DP(u,x),min(si[x]+si[u],K));~i;i--)
                for (int k=max(i-si[x],0);k<=si[u]&&k<=i;k++)
                    f[x][i]=max(f[x][i],f[x][i-k]+f[u][k]+val(k));
            si[x]+=si[u];
        }
}
int main(){
    freopen("program.in","r",stdin);
    freopen("program.out","w",stdout);
    for (int i=(scanf("%d%d",&n,&K),1),x,y,z;i<n;i++)
        scanf("%d%d%d",&x,&y,&z),Add(x,y,z),Add(y,x,z);
    return DP(1),printf("%lld\n",f[1][K]),0;
}