#P6694. [2019山东省队集训第一轮]喜欢最最痛
[2019山东省队集训第一轮]喜欢最最痛
[2019山东省队集训第一轮]喜欢最最痛
题目背景
分开了哦算,
自身的成功。
喜欢最最痛,
最成功租房。
——龚诗锋《么片对棠》
题目描述
给定一棵有 个结点的带权树,所有边权均为正整数。
你需要从结点 出发,经过所有原树边至少一次,最终回到结点 。允许重复经过边,每次经过的边权都计入总成本。
你可以按顺序添加额外的无向边,第 条添加的边权为 ,它的两个端点可以自行选择。最终的行走路线不必经过所有已添加的额外边。
对于每个 ,求最多允许添加 条额外边时的最小行走成本。
由于添加后可以不使用,允许添加 条等价于拥有前 个权值 对应的额外边,并可只使用其中一部分。不同的 分别求解。
输入格式
第一行两个正整数 。
接下来 行,每行三个整数 ,表示原树中一条连接 、权值为 的无向边。
接下来一行 个正整数 。
输出格式
输出 个整数。第 个数表示最多允许添加 条额外边时的最小成本,其中 。
样例输入
5 5
2 3 7
1 3 6
5 2 3
4 3 9
6 3 6 1 5
样例输出
50 37 34 34 29 29
其他样例
原题样例 2 见选手目录下的 love/love2.in 和 love/love2.ans,其范围符合子任务 2。
原题样例 3 见选手目录下的 love/love3.in 和 love/love3.ans,其范围符合子任务 4。
数据范围
所有数据满足 ,。
| 子任务 | 分值 | 的上界 | 的上界 | 特殊性质 |
|---|---|---|---|---|
| 1 | 10 分 | 无 | ||
| 2 | 20 分 | |||
| 3 | 10 分 | |||
| 4 | 5 分 | 所有原树边均有一个端点为 | ||
| 5 | 55 分 | 无 | ||