P17019 [ROI 2026 Day1] Investigation in Temeria

Temeria is one of the most powerful kingdoms in the north, and its capital is the city of Wyzima. The sorceress Triss lives in Wyzima. She has sensed a strong magical anomaly and decides to investigate the Kingdom of Temeria to find the source of the anomaly. Temeria has $n$ cities, numbered from $1$ to $n$, where the capital Wyzima is numbered $1$. The cities are connected by $n - 1$ bidirectional roads. The $i$-th road connects cities $u_i$ and $v_i$ and has length $w_i$. It is guaranteed that Triss can travel from any city to any other city using only these roads. Triss plans to set out from Wyzima, eventually return to Wyzima, and visit all $n$ cities along the way. She can walk along roads, but it is slow. She has $k$ teleportation crystals, which can be used to instantly move between cities. At any time, Triss may leave a crystal in the city she is currently in. Later, she may use a previously left crystal to instantly return to the city where she left that crystal, along the shortest path. After being used, the crystal will shatter. Triss may leave and use crystals in any order. Unfortunately, teleportation does not leave no trace. Specifically, if Triss uses a crystal in city $a$ and arrives at city $b$, then all cities on the shortest path from $a$ to $b$ (including $a$ and $b$) will leave magical traces, and all later teleportation routes may no longer pass through these cities. Please help Triss. For each $j$ (from $1$ to $k$, inclusive), find the minimum total distance she needs to walk in order to visit all cities in the kingdom and return to Wyzima, using at most $j$ crystals.

The first line contains two integers $n$ and $k$ ($2 \le n \le 500\,000$; $1 \le k \le n$), representing the number of cities and the number of teleportation crystals Triss has. The next $n - 1$ lines describe the roads. Each line contains three integers $u_i$, $v_i$, and $w_i$ ($1 \le u_i, v_i \le n$; $1 \le w_i \le 10^9$), representing the two cities connected by the $i$-th road and its length.

Output $k$ integers. The $j$-th integer denotes the minimum total distance Triss needs to walk to visit all cities and return to Wyzima, under the condition that she uses at most $j$ crystals.

### Explanation In the first sample, Triss’s optimal route is as follows: - Triss leaves a crystal in city $1$, then walks along the route $1 \to 2 \to 1 \to 3 \to 4 \to 3 \to 5$, and then uses the crystal to instantly return to city $1$. In the second sample, the optimal route is as follows: - Triss walks along the route $1 \to 5 \to 1$, then leaves a crystal in city $1$, then walks along the route $1 \to 9 \to 1 \to 2 \to 3 \to 7 \to 3 \to 4 \to 8 \to 4 \to 6 \to 10$, and uses the crystal in city $1$. The length of this route is $86$, and Triss uses exactly one crystal. In another plan, Triss needs to use two crystals, denoted $x$ and $y$: - Triss leaves crystal $x$ in city $1$; - Then she walks along the route $1 \to 5 \to 1 \to 9 \to 1 \to 2 \to 3 \to 7 \to 3 \to 4 \to 6$; - She leaves crystal $y$ in city $6$; - Then she walks from $6$ to $10$, and uses crystal $y$ to return to city $6$; - Then she walks along the route $6 \to 4 \to 8$; - Finally, she uses crystal $x$ to end the trip. ### Subtasks | Subtask | Score | $n$, $k$ | Additional Constraints | Dependent Subtasks | |:---:|:---:|:---:|:---|:---:| | 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$ | Complete binary tree$^{*}$, $w_i = 1$ | | | 6 | 11 | $n \le 150\,000$ | $w_i = 1$ | 5 | | 7 | 15 | $n \le 150\,000$ | Special graph$^{**}$ | | | 8 | 12 | $n \le 150\,000$ | Each city has at most $10$ roads | | | 9 | 11 | $n \le 150\,000$ | | 1 – 8 | | 10 | 4 | $n \le 300\,000$ | | 1 – 9 | | 11 | 3 | $n \le 500\,000$ | | 1 – 10 | $^{*}$ The **complete binary tree** in subtask 5 refers to a tree consisting of $2^s - 1$ vertices ($n = 2^s - 1$), where for each $i$ ($1 \le i \le 2^{s-1} - 1$), there are edges $(i, 2i)$ and $(i, 2i + 1)$. $^{**}$ The **special graph** in subtask 7 refers to a tree consisting of an odd number $n$ of vertices, where for each $i$ ($1 \le i \le \frac{n-1}{2}$), there are edges $(1, 2i)$ and $(2i, 2i + 1)$. :::align{center}  ::: Translated by ChatGPT 5