RXD and dividing

题目链接

题意

有一棵n个点的树，每条边有边权，现在要求将$2,3,4…n$划分成$k$部分，定义$f(S)$为$S$集合的最小斯坦纳树的边权和。
求$res=\sum_{i=1}^{k}f({1} \bigcup S_{i})$最大。

思路

首先解释一下什么是斯坦纳树。

斯坦纳树

斯坦纳树允许在给定的集合外多加一些点，使得总开销最小。
最小生成树是一种特殊的斯坦纳树。

贪心

按照贡献计算，每个几何最后都要和1号点也就是根结点连通，所以如果选择他或他的子结点作为一个集合的一部分，那么它上面这条边能产生$w_{i}$的贡献，他最大贡献即是$w_{i} \times min(size(u), k)$，只要$dfs$一下就可以了。