#P11340. [RMI 2021] 路径 / Paths

    ID: 10505 传统题 1000ms 256MiB 尝试: 2 已通过: 2 难度: 8 上传者: 标签>CF2400树形DP贪心线段树最短路动态规划数据结构

[RMI 2021] 路径 / Paths

题目描述

橘猫有一棵树 T=(V,E)T=(V,E),边有边权。其中 ∣V∣=n|V|=n。

令 path⁡(u,v)\operatorname{path}(u,v) 为 u,vu,v 间最短路径上的边集。

对于根节点 root\mathrm{root},定义点集 V′⊆VV'\subseteq V 的路径并为 $\displaystyle E'(V')=\bigcup_{u\in V'} \operatorname{path}(\mathrm{root},u)$。在此基础上,定义 V′V' 的权值为 ∑(u,v,w)∈E′(V′)w\displaystyle \sum_{(u,v,w)\in E'(V') } w,即路径并的边权和。

给定正整数 kk。定义 f(u)f(u) 为:当 uu 为根时,在 (nk){n\choose k} 种选择 V′⊆VV'\subseteq V 且 ∣V′∣=k|V'|=k 的方案中,V′V' 权值的最大值。

对于 u=1,2,⋯ ,nu=1,2,\cdots,n,橘猫请你帮她求出 f(u)f(u) 的值。

输入格式

第一行,两个正整数 n,kn,k。

接下来 (n−1)(n-1) 行,每行三个整数 u,v,wu,v,w,表示 (u,v,w)∈E(u,v,w)\in E。

输出格式

输出 nn 行,第 ii 行一个整数表示 f(i)f(i)。

输入输出样例 #1

输入 #1

11 3
1 2 5
2 3 3
2 6 5
3 4 4
3 5 2
1 7 6
7 8 4
7 9 5
1 10 1
10 11 1

输出 #1

28
28
28
32
30
32
28
32
32
29
30

说明/提示

样例解释

u=1u=1 时,一种最优方案是选择 V′={4,6,9}V'=\{4,6,9\}。

数据范围

对于 100%100\% 的数据,保证:

  • 1≤k≤n≤1051\le k\le n\le 10^5;
  • 0≤w≤1090\le w\le 10^9。
子任务编号 n≤n\le k≤k\le 得分
1 1 18 18 nn 88
2 2 200 200 2020 1111
3 3 103 10^3 100100 1717
4 4 2×103 2\times 10^3 nn 2020
5 5 105 10^5 11 1212
6 6 105 10^5 nn 3232