长沙网站 建设推广世云网络/外链推广网站
Description
有一棵点数为 N 的树，树边有边权。给你一个在 0~ N 之内的正整
数 K ，你要在这棵树中选择 K个点，将其染成黑色，并将其他 的
N-K个点染成白色 。 将所有点染色后，你会获得黑点两两之间的距
离加上白点两两之间的距离的和的受益。问受益最大值是多少。
Input
第一行包含两个整数 N, K 。
接下来 N-1 行每行三个正整数 fr, to, dis ， 表示该树中存在一条长度
为 dis 的边 (fr, to) 。输入保证所有点之间是联通的。
Output
输出一个正整数，表示收益的最大值。
Sample Input
3 1
1 2 1
1 3 2
1 2 1
1 3 2
Sample Output
3
HINT
对于 100% 的数据， 0<=K<=N <=2000
Source
鸣谢bhiaibogf提供
我们用fij表示以i为根的子树里选了k个节点，整棵树的ans。那么我们考虑转移，t为i的一个孩子，fij=fix+ft(j-x)+len*((j-x)*(k-(j-x))+(size[t]-(j-x))*(n-k-(size[t]-(j-x))))
然后问题就解决了！这个复杂度是O(n^2)的
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
long long f[2001][2001];
struct line
{int s,t;long long x;int next;
}a[4001];
int head[2001];
long long tmp[2001];
int edge;
inline void add(int s,int t,long long x)
{a[edge].next=head[s];head[s]=edge;a[edge].s=s;a[edge].t=t;a[edge].x=x;
}
bool v[2001];
int size[2001];
int n,kk;
inline void trdp(int d)
{v[d]=true;size[d]=1;int i;int j,k;for(i=head[d];i!=0;i=a[i].next){int t=a[i].t;if(!v[t]){trdp(t);for(j=0;j<=kk;j++)tmp[j]=f[d][j];for(j=0;j<=min(size[d],kk);j++){for(k=0;k<=min(size[t],kk);k++){if(j+k>kk)break;//int m=j+k;tmp[j+k]=max(tmp[j+k],f[d][j]+f[t][k]+a[i].x*(k*(kk-k)+(size[t]-k)*(n-kk-(size[t]-k))));}}size[d]+=size[t];for(j=0;j<=size[d];j++)f[d][j]=max(f[d][j],tmp[j]);}}
}
int main()
{scanf("%d%d",&n,&kk);int i;int s,t;long long x;for(i=1;i<=n-1;i++){scanf("%d%d%lld",&s,&t,&x);edge++;add(s,t,x);edge++;add(t,s,x);}trdp(1);printf("%lld\n",f[1][kk]);return 0;
}