BZOJ4033 T1

时间:2022-06-10 11:56:14

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

Sample Output

3

HINT

对于\(100\%\)的数据,\(0 \le K \le N \le 2000\)。

一道很好的树形dp题。\(f_{i,j}\)表示以\(i\)为根的子树中染\(j\)个黑点的最大收益,那么问题就来了,应该怎么转移?

假设我们此时已经dp到\(now\)这个跟,试着更新\(f_{now,j}\),现在用其儿子\(c\)来更新。假设连接\(now\)和\(c\)的边权值\(dis\),枚举\(f_{c,k}\),之后就计算此边贡献即可。黑点这条边经过了\((K-k) \times k\)次(所有黑点,并不只是\(now\)子树中),故贡献\((K-k) \times k \times dis\)。白点也这样算即可。故转移方程为

\[f_{now,j} = max(f_{now,j},f_{now,j-k}+f_{c,k}+(K-k) \times k \times dis+(N-K-(size-k)) \times (size-k) \times dis)
\]

其中\(size\)为\(c\)的子树大小。

代码如下:

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std; #define maxn (2010)
typedef long long ll;
int cnt,N,K,len[maxn*2],next[maxn*2],toit[maxn*2],side[maxn]; ll f[maxn][maxn]; inline void add(int a,int b,int c) { next[++cnt] = side[a]; side[a] = cnt; toit[cnt] = b; len[cnt] = c; }
inline void ins(int a,int b,int c) { add(a,b,c); add(b,a,c); } inline void upd(ll &a,ll b) { a = max(a,b); } inline int dfs(int now,int fa)
{
int sz = 1;
memset(f[now],128,sizeof(f[now])); f[now][0] = f[now][1] = 0;
for (int i = side[now];i;i = next[i])
{
if (toit[i] == fa) continue;
int num = dfs(toit[i],now);
for (int j = min(K,sz += num);j >= 0;--j)
for (int k = 0;k <= num&&k <= j;++k)
upd(f[now][j],((ll)(K-k)*(ll)k+(ll)(N-K-(num-k))*(ll)(num-k))*(ll)len[i]+f[toit[i]][k]+f[now][j-k]);
}
return sz;
} int main()
{
freopen("4033.in","r",stdin);
freopen("4033.out","w",stdout);
scanf("%d %d",&N,&K);
for (int i = 1,a,b,c;i < N;++i) scanf("%d %d %d",&a,&b,&c),ins(a,b,c);
dfs(1,0);
printf("%lld",f[1][K]);
fclose(stdin); fclose(stdout);
return 0;
}