Description

有一棵点数为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

5 2
1 2 3
1 5 1
2 3 1
2 4 2

Sample Output

17
【样例解释】
将点1,2染黑就能获得最大收益。

HINT

2017.9.12新加数据一组 By GXZlegend

Source

鸣谢bhiaibogf提供

树形dp

设dp[x][i]表示在x子树内选择了i个黑点 对答案做出的贡献最大是多少

这样定义方便dp 方程很好写dp[x][i+j]=max(dp[x][i]+dp[y][j]+(ll)j*(k-j)*z+(ll)(size[y]-j)*(n-k-size[y]+j)*z)) y就是x的子树

仍然有一些实现的细节

乍一看应该是n^3 但是仔细想 如果只利用合法状态进行dp的话可以发现

每次相当于在子树内枚举了所有以这个点作为lca的点对状态

复杂度证明https://www.cnblogs.com/GXZlegend/p/7040678.html

 


elijahqi

退役了 现在在商院 偶尔打CF,有时有ACM regional也去玩一下

发表评论