bzoj4033（树上染色）

　　　　　　　　　　　　　　　　　　　　　　　　　　树上染色

有一棵点数为N的树，树边有边权。给你一个在0~N之内的正整数K，你要在这棵树中选择K个点，将其染成黑色，并

将其他的N-K个点染成白色。将所有点染色后，你会获得黑点两两之间的距离加上白点两两之间距离的和的收益。

问收益最大值是多少。

Input

第一行两个整数N,K。

接下来N-1行每行三个正整数fr,to,dis，表示该树中存在一条长度为dis的边(fr,to)。

输入保证所有点之间是联通的。

N<=2000,0<=K<=N

Output

输出一个正整数，表示收益的最大值。

Sample Input

Sample Output

17
【样例解释】
将点1,2染黑就能获得最大收益。
一道河北省选题，树形dp，写代码的时候注释都写上去了，F[I][J]表示以i为根，选了j个黑点的最大值。

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<iostream>
 4 #include<cmath>
 5 #include<cstring>
 6 using namespace std;
 7 
 8 typedef long long LL;
 9 const LL INF=1e16+7;
10 const int NN=2007;
11 
12 int n,k;
13 int size[NN];
14 int cnt=0,head[NN],next[NN*2],rea[NN*2],val[NN*2];
15 LL f[NN][NN];
16 
17 void add(int u,int v,int fee)
18 {
19     cnt++;
20     next[cnt]=head[u];
21     head[u]=cnt;
22     rea[cnt]=v;
23     val[cnt]=fee;
24 }
25 void dfs(int u,int fa)
26 {
27     f[u][0]=f[u][1]=0;//没什么好说的吧。 
28     size[u]=1;
29     for (int i=head[u];i!=-1;i=next[i])
30     {
31         int v=rea[i],fee=val[i];
32         if (v==fa) continue;
33         dfs(v,u);
34         size[u]+=size[v];
35         for (int j=size[u];j>=0;j--)
36         {
37             LL ans=0;
38             for (int t=0;t<=size[v]&&t<=j;t++)//防止越界 
39             {
40                 ans=(long long)(t*(k-t))+(long long)((size[v]-t)*(n-k-(size[v]-t)));//和所有的黑点，白点的连边（n-k）为所有的白点。 
41                 ans*=fee;//乘上这条边。 
42                 ans+=f[v][t];//加上这棵子树上的贡献。 
43                 f[u][j]=max(f[u][j],f[u][j-t]+ans);//因为从大到小，所以如果，u的左边子树不够支持j-t的话，绝对是没有值的。 
44             }
45         }
46     }
47 }
48 void init()
49 {
50     memset(head,-1,sizeof(head));
51     int x,y,z;
52     scanf("%d%d",&n,&k);
53     for (int i=1;i<n;i++)
54     {
55         scanf("%d%d%d",&x,&y,&z);
56         add(x,y,z),add(y,x,z);
57     }
58     for (int i=1;i<=n;i++)
59         for (int j=1;j<=n;j++)
60             f[i][j]=-INF;
61     dfs(1,-1);
62     printf("%lld
",f[1][k]);//1为根节点。 
63 }
64 int main()
65 {
66     init();
67 }