P15455 [JOI 2026 SemiFinal] New Bridge / New Bridge

The country of JOI consists of $N$ islands, numbered from $1$ to $N$. Currently, there are no bridges connecting the islands, so life is very inconvenient for the residents. Therefore, as a minister of the country of JOI, you decide to build new bridges as a national project. There are $M$ bridge construction plans. The $j$-th plan ($1 \le j \le M$) is to build a two-way bridge between islands $A_j$ and $B_j$ with cost $C_j$. It is guaranteed that $C_1, C_2, \dots, C_M$ are all distinct. It is also guaranteed that if all construction plans are carried out, then all islands will be mutually reachable via some bridges. Because the budget of the country of JOI is limited, you decide to carry out the national project in the following way: 1. Choose one island $s$ from the $N$ islands, and make it the capital. 2. Perform the following operation $N - 1$ times: - Before each operation, call the islands that are reachable from the capital via some bridges **near islands**, and call the other islands **far islands**. Among the construction plans whose one endpoint is a near island and the other endpoint is a far island, choose the one with the smallest cost and carry it out. 3. After performing the operation $N - 1$ times, the national project ends. From the constraints satisfied by the construction plans, the following facts can be proved: - In each operation, there is always at least one construction plan that can be chosen. Also, the construction plan that is carried out is uniquely determined. - When the project ends, all islands are mutually reachable via some bridges. Rin, who is considering moving to the country of JOI, decides to compute the “inconvenience” of each island in the following way in order to decide which island to live on. The inconvenience of island $i$ ($1 \le i \le N$) is defined as follows: - Let $D_{s,i}$ be the number of construction plans carried out until island $i$ becomes reachable from the capital, when the national project is carried out with island $s$ ($1 \le s \le N$) as the capital. Here, when $s = i$, $D_{s,i}$ is $0$. - The inconvenience of island $i$ is the sum of $D_{s,i}$ over all $1 \le s \le N$. Rin wants to compute the inconvenience of $Q$ candidate islands $X_1, X_2, \dots, X_Q$ that she is considering. Given the construction plans and the candidate islands, write a program to find the inconvenience of these islands.

Input is given from standard input in the following format: $N\ M\ Q$ $A_1\ B_1\ C_1$ $A_2\ B_2\ C_2$ $\vdots$ $A_M\ B_M\ C_M$ $X_1$ $X_2$ $\vdots$ $X_Q$

Output $Q$ lines. In the $k$-th line, output the inconvenience of island $X_k$ ($1 \le k \le Q$).

#### Sample Explanation 1 For example, consider the case where the national project is carried out with island $1$ as the capital. Then, the construction plans will be carried out in the following order: 1. Carry out the $1$-st construction plan. Island $3$ becomes newly reachable from the capital. 2. Carry out the $3$-rd construction plan. Island $2$ becomes newly reachable from the capital. 3. Carry out the $5$-th construction plan. Island $4$ becomes newly reachable from the capital. Thus, $D_{1,1} = 0,\ D_{1,2} = 2,\ D_{1,3} = 1,\ D_{1,4} = 3$. Since $D_{2,1} = 2,\ D_{3,1} = 2,\ D_{4,1} = 3$, the inconvenience of island $1$ is $D_{1,1} + D_{2,1} + D_{3,1} + D_{4,1} = 0 + 2 + 2 + 3 = 7$. Also, since $D_{2,3} = 1,\ D_{3,3} = 0,\ D_{4,3} = 1$, the inconvenience of island $3$ is $D_{1,3} + D_{2,3} + D_{3,3} + D_{4,3} = 1 + 1 + 0 + 1 = 3$. This sample input satisfies the constraints of subtasks $1, 2, 6$. ### Constraints - $2 \le N \le 300\,000$ - $1 \le M \le 600\,000$ - $1 \le Q \le N$ - $1 \le A_j < B_j \le N$（$1 \le j \le M$） - If all construction plans are carried out, all islands are mutually reachable via some bridges - $1 \le C_j \le 10^9$（$1 \le j \le M$） - $C_1, C_2, \dots, C_M$ are all distinct - $1 \le X_k \le N$（$1 \le k \le Q$） - $X_1, X_2, \dots, X_Q$ are all distinct - All input values are integers ### Subtasks 1. (5 points) $N \le 2000,\ M \le 2000$ 2. (8 points) $N \le 2000$ 3. (9 points) $M = N - 1$, and $A_j = j,\ B_j = j + 1$（$1 \le j \le M$）, $Q = 1$ 4. (18 points) $M = N - 1$, and $A_j = j,\ B_j = j + 1$（$1 \le j \le M$） 5. (28 points) $Q = 1$ 6. (32 points) No additional restrictions Translated by DeepSeek. Translated by ChatGPT 5