P11317 [RMI 2021] 路径 / Paths

译自 [9th Romanian Master of Informatics, RMI 2021](https://rmi.lbi.ro/rmi_2021/) D2T2。$\texttt{0.3s,0.5G}$。 

橘猫有一棵树 $T=(V,E)$，边有边权。其中 $|V|=n$。 令 $\operatorname{path}(u,v)$ 为 $u,v$ 间最短路径上的边集。 对于根节点 $\mathrm{root}$，定义点集 $V'\subseteq V$ 的**路径并**为 $\displaystyle E'(V')=\bigcup_{u\in V'} \operatorname{path}(\mathrm{root},u)$。在此基础上，定义 $V'$ 的**权值**为 $\displaystyle \sum_{(u,v,w)\in E'(V') } w$，即路径并的边权和。 给定正整数 $k$。定义 $f(u)$ 为：当 $u$ 为根时，在 ${n\choose k}$ 种选择 $V'\subseteq V$ 且 $|V'|=k$ 的方案中，$V'$ 权值的最大值。 对于 $u=1,2,\cdots,n$，橘猫请你帮她求出 $f(u)$ 的值。

无

无

#### 样例解释 $u=1$ 时，一种最优方案是选择 $V'=\{4,6,9\}$。  #### 数据范围 对于 $100\%$ 的数据，保证： - $1\le k\le n\le 10^5$； - $0\le w\le 10^9$。 | 子任务编号 | $n\le $ | $k\le$ |得分 | | :--: | :--: | :--: | :--: | | $ 1 $ | $ 18 $ | $n$ | $8$ | | $ 2 $ | $ 200 $ | $20$ | $11$ | | $ 3 $ | $ 10^3 $ | $100$ | $17$ | | $ 4 $ | $ 2\times 10^3 $ | $n$ | $20$ | | $ 5 $ | $ 10^5 $ | $1$ | $12$ | | $ 6 $ | $ 10^5$ | $n$ | $32$ |