P17019 [ROI 2026 Day1] 泰莫利亚的调查

泰莫利亚是北方最强大的王国之一，首都是维吉玛城。女术士特莉丝住在维吉玛城，她察觉到了强烈的魔法异常，决定调查泰莫利亚王国以找到异常的源头。 泰莫利亚有 $n$ 座城市，编号为 $1$ 到 $n$，首都维吉玛的编号为 $1$。城市之间由 $n - 1$ 条双向道路连接，第 $i$ 条道路连接城市 $u_i$ 和 $v_i$，长度为 $w_i$。保证特莉丝仅靠这些道路便可以从任意一座城市到达任意另一座城市。 特莉丝计划从维吉玛出发，最终回到维吉玛，并途经全部 $n$ 座城市。她可以沿道路行走，但这很慢。她拥有 $k$ 个传送水晶，可以用来在城市之间瞬间移动。 特莉丝可以在任意时刻将水晶留在当前所在的城市。之后，她可以使用此前留下的水晶，沿最短路径瞬间返回到她留下该水晶的城市。使用后水晶会碎裂。特莉丝可以按任意顺序留下和使用水晶。遗憾的是，传送并非不留痕迹。具体而言，如果特莉丝在城市 $a$ 使用水晶并到达城市 $b$，那么在从 $a$ 到 $b$ 的最短路径上的所有城市（包括 $a$ 和 $b$）都会留下魔法痕迹，此后的传送路线不能再经过这些城市。 请帮助特莉丝。对每个 $j$（从 $1$ 到 $k$，包含 $k$），求出她最多使用 $j$ 个水晶便走遍王国所有城市并返回维吉玛所需走过的最小总距离。

第一行包含两个整数 $n$ 和 $k$（$2 \le n \le 500\,000$；$1 \le k \le n$），分别表示城市数量以及特莉丝拥有的传送水晶数量。 接下来的 $n - 1$ 行描述道路：每行包含三个整数 $u_i$、$v_i$ 和 $w_i$（$1 \le u_i, v_i \le n$；$1 \le w_i \le 10^9$），分别表示第 $i$ 条道路连接的两座城市及其长度。

输出 $k$ 个整数，其中第 $j$ 个数表示在使用不超过 $j$ 个水晶的前提下，特莉丝走遍所有城市并返回维吉玛所需走过的最小总距离。

### 说明 在第一个样例中，特莉丝的最优路线如下： - 特莉丝在城市 $1$ 留下一个水晶，然后沿路线 $1 \to 2 \to 1 \to 3 \to 4 \to 3 \to 5$ 行走，之后使用水晶，瞬间返回城市 $1$。 在第二个样例中，最优路线如下： - 特莉丝沿路线 $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$ 行走，并在城市 $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$ 走到 $10$，使用水晶 $y$ 返回城市 $6$； - 再沿路线 $6 \to 4 \to 8$ 行走； - 最后使用水晶 $x$ 结束行程。 ### 子任务 | 子任务 | 分数 | $n$、$k$ | 额外限制 | 依赖子任务 | |:---:|:---:|:---:|:---|:---:| | 1 | 9 | $n \le 150\,000$；$k = 1$ | | | | 2 | 5 | $n \le 100$ | | У | | 3 | 10 | $n \le 5\,000$ | | 2 | | 4 | 9 | $n \le 150\,000$；$k \le 300$ | | 1 – 2 | | 5 | 11 | $n \le 150\,000$ | 完全二叉树$^{*}$，$w_i = 1$ | | | 6 | 11 | $n \le 150\,000$ | $w_i = 1$ | 5 | | 7 | 15 | $n \le 150\,000$ | 特殊图$^{**}$ | | | 8 | 12 | $n \le 150\,000$ | 每座城市至多有 $10$ 条道路 | | | 9 | 11 | $n \le 150\,000$ | | 1 – 8 | | 10 | 4 | $n \le 300\,000$ | | 1 – 9 | | 11 | 3 | $n \le 500\,000$ | | 1 – 10 | $^{*}$ 子任务 5 中的**完全二叉树**是指由 $2^s - 1$ 个顶点构成的树（$n = 2^s - 1$），其中对于每个 $i$（$1 \le i \le 2^{s-1} - 1$），存在边 $(i, 2i)$ 和 $(i, 2i + 1)$。 $^{**}$ 子任务 7 中的**特殊图**是指由奇数 $n$ 个顶点构成的树，其中对于每个 $i$（$1 \le i \le \frac{n-1}{2}$），存在边 $(1, 2i)$ 和 $(2i, 2i + 1)$。 :::align{center}  ::: 翻译由 DeepSeek V4 Pro 完成