#5754. 「ROI 2026 Day1」泰莫利亚调查

标签: 传统 | 时间限制: 2000 ms | 内存限制: 1024 MiB |

题目描述

译自 ROI 2026 Day1 T2. Расследование в Темерии

泰莫利亚（Temeria）是北方最强大的王国之一，其首都是维济玛（Vyzima）。居住在维济玛的女巫特莉丝（Triss）发现了强烈的魔法异常，并决定探索泰莫利亚王国以寻找其源头。

泰莫利亚共有 $n$ 座城市，编号为从 $1$ 到 $n$，首都维济玛的编号为 $1$。这些城市由 $n-1$ 条双向道路连接，第 $i$ 条道路连接城市 $u_i$ 和 $v_i$，其长度为 $w_i$。保证特莉丝仅通过这些道路即可从任意一座城市到达另一座城市。

特莉丝计划从维济玛出发并最终回到维济玛，期间走遍所有的 $n$ 座城市。 特莉丝可以沿道路行走，但这样速度较慢。她拥有 $k$ 颗传送水晶，可以利用它们在城市之间进行瞬间移动。

在任何时刻，特莉丝都可以在她当前所在的城市留下一个水晶。随后，这位女巫可以利用之前留下的水晶，沿最短路径瞬间回到该水晶所在的城市。使用后，水晶会损毁。特莉丝可以按任意顺序放置和使用水晶。 遗憾的是，传送会留下痕迹。具体来说，若特莉丝在城市 $a$ 使用水晶并传送到了城市 $b$，那么位于 $a$ 到 $b$ 最短路径上的所有城市（包括 $a$ 和 $b$）都会留下魔法痕迹。此后，其他的传送路线都不能经过这些留有痕迹的城市。

请帮助特莉丝解决这个问题。对于从 $1$ 到 $k$ 之间的每一个 $j$，确定在花费不超过 $j$ 颗水晶的前提下，走遍所有城市并返回维济玛所需的最小步行距离。

输入格式

第一行包含两个整数 $n$ 和 $k$ $(2 \leq n \leq 500\,000; 1 \leq k \leq n)$，分别表示城市的数量和特莉丝拥有的传送水晶数量。

接下来的 $n-1$ 行包含道路的描述：每行有三个整数 $u_i, v_i$ 和 $w_i$ $(1 \leq u_i, v_i \leq n; 1 \leq w_i \leq 10^9)$，分别表示第 $i$ 条道路连接的两座城市编号及其长度。

输出格式

输出 $k$ 个整数，其中第 $j$ 个整数表示：在花费不超过 $j$ 颗水晶的前提下，走遍所有城市并返回维济玛所需的最小距离。

样例 1

输入

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

输出

6

在第一个样例中，特莉丝的最优路线如下：

• 特莉丝在城市 $1$ 留下水晶，然后沿路线 $1 \to 2 \to 1 \to 3 \to 4 \to 3 \to 5$ 行进，随后使用水晶，瞬间回到城市 $1$。

样例 2

输入

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

输出

86
85

在第二个样例中，最优路线如下：

• 特莉丝沿路线 $1 \to 5 \to 1$ 行进，然后在城市 $1$ 留下水晶，接着沿路线 $1 \to 9 \to 1 \to 2 \to 3 \to 7 \to 3 \to 4 \to 8 \to 4 \to 6 \to 10$ 行进，并在城市 $10$ 使用水晶回到城市 $1$。该路线的长度为 $86$，且特莉丝恰好使用了一颗水晶。

在另一种路线中，特莉丝需要使用两颗水晶，分别记为 $x$ 和 $y$：

• 特莉丝在城市 $1$ 留下水晶 $x$；
• 接着沿路线 $1 \to 5 \to 1 \to 9 \to 1 \to 2 \to 3 \to 7 \to 3 \to 4 \to 6$ 行进；
• 在城市 $6$ 特莉丝留下水晶 $y$；
• 然后前往 $6 \to 10$ 并在城市 $10$ 使用水晶 $y$ 回到城市 $6$；
• 沿路线 $6 \to 4 \to 8$ 行进；
• 最后通过使用水晶 $x$ 结束她的旅程。

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。

• 子任务 $5$ 中的完美二叉树是指包含 $2^s-1$ 个节点（$n = 2^s-1$）的树，其中对于 $1$ 到 $2^{s-1}-1$ 之间的每个 $i$，都存在两 selection 条边 $(i, 2i)$ 和 $(i, 2i+1)$。
• 子任务 $7$ 中的特殊图是指包含奇数个节点 $n$ 的树，其中对于 $1$ 到 $\frac{n-1}{2}$ 之间的每个 $i$，都存在两条边 $(1, 2i)$ 和 $(2i, 2i+1)$。