新たな橋(New Bridge)

JOI 国はN 個の島からなる国であり,各島には1 からN までの番号が付けられている.現在,この国に
は島と島の間を結ぶ橋が存在しておらず,住民は不便な生活を送っている.
そこで,JOI 国の大臣であるあなたは国家事業として新たに橋を架けることにした.橋を架ける建設計画
がM 個あり,j 番目(1 ≦j ≦M) の建設計画は,費用C j をかけて,島Aj と島Bj の間を双方向に結ぶ橋を
架けるものである.ここで,C1,C2, . . . ,CM は相異なることが保証される.また,すべての建設計画を実行
した場合において,すべての島がいくつかの橋によって互いに到達可能になることが保証される.
JOI 国の予算は限られているので,あなたは,次のように国家事業を実施することに決めた.
1. N 個の島の中からひとつの島s を選び,その島を首都とする.
2. 以下の操作をN −1 回行う.
• 各操作をする前の時点で,いくつかの橋を用いて首都から到達可能である島を近い島,そうでな
い島を遠い島とする.架ける橋の一端が近い島,もう一端が遠い島であるような建設計画のう
ち,費用が最も安いものを選び,実行する.
3. 操作をN −1 回行った後,国家事業を終了する.
ここで,建設計画の満たす制約より,以下の事柄を証明できる.
• 各操作において,選ぶことのできる建設計画は必ず存在する.さらに,実行される建設計画は一意に
定まる.
• この事業が終了した時点で,すべての島がいくつかの橋によって互いに到達可能になる.
JOI 国への移住を検討している凛は,どの島に住むかの参考にするため,次のように各島の不便度を計算
することにした.島i (1 ≦i ≦N) の不便度は次のように定義される.
• 島s (1 ≦s ≦N) を首都として国家事業を実施したときに,島i が首都から到達可能になるまでに実
行された建設計画の数をDs,i とする.ここで,s = i のときはDs,i は0 とする.
• 島i の不便度は,すべての1 ≦s ≦N に対するDs,i の総和とする.
凛は,引っ越し先の候補としているQ 個の島X1, X2, . . . , XQ の不便度を計算したい.建設計画と引っ越し
先の候補の島の情報が与えられたとき,これらの島の不便度を求めるプログラムを作成せよ.

The 25^th Japanese Olympiad in Informatics (JOI 2025/2026)
Semifinal Stage
February 1, 2026 (Shimbashi, Tokyo)

• 2 ≦N ≦300 000.
• 1 ≦M ≦600 000.
• 1 ≦Q ≦N.
• 1 ≦A j < Bj ≦N (1 ≦j ≦M).
• すべての建設計画を実行した場合において,すべての島がいくつかの橋によって互いに到達可能に
なる.
• 1 ≦C j ≦109 (1 ≦j ≦M).
• C1,C2, . . . ,CM は相異なる.
• 1 ≦Xk ≦N (1 ≦k ≦Q).
• X1, X2, . . . , XQ は相異なる.
• 入力される値はすべて整数である.

The 25^th Japanese Olympiad in Informatics (JOI 2025/2026)
Semifinal Stage
February 1, 2026 (Shimbashi, Tokyo)

1. (5 点) N ≦2 000,M ≦2 000.
2. (8 点) N ≦2 000.
3. (9 点) M = N −1,Aj = j, Bj = j + 1 (1 ≦j ≦M),Q = 1.
4. (18 点) M = N −1,A j = j, Bj = j + 1 (1 ≦j ≦M).
5. (28 点) Q = 1.
6. (32 点) 追加の制約はない.

入力は以下の形式で標準入力から与えられる.
N M Q
A1 B1 C1
A2 B2 C2
...
AM BM CM
X1
X2
...
XQ

Q 行出力せよ.k 行目には,島Xk (1 ≦k ≦Q) の不便度を出力せよ.

생성자가 기록되지 않았습니다.

출처 JOI 2026 Semifinal