AT_joi2026_semifinal_e 新たな橋 (New Bridge)

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

入力は以下の形式で標準入力から与えられる． > $ 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 $

$ Q $ 行出力せよ． $ k $ 行目には，島 $ X_k $ ( $ 1 \leqq k \leqq Q $ ) の不便度を出力せよ． ---

### 小課題 1. ( $ 5 $ 点) $ N \leqq 2\,000 $ ， $ M \leqq 2\,000 $ ． 2. ( $ 8 $ 点) $ N \leqq 2\,000 $ ． 3. ( $ 9 $ 点) $ M = N - 1 $ ， $ A_j = j, B_j = j + 1 $ ( $ 1 \leqq j \leqq M $ )， $ Q = 1 $ ． 4. ( $ 18 $ 点) $ M = N - 1 $ ， $ A_j = j, B_j = j + 1 $ ( $ 1 \leqq j \leqq M $ )． 5. ( $ 28 $ 点) $ Q = 1 $ ． 6. ( $ 32 $ 点) 追加の制約はない． --- ### Sample Explanation 1 例えば，島 $ 1 $ を首都として，国家事業を実施した場合を考える．このとき，次のように建設計画が実行される． 1. $ 1 $ 番目の建設計画が実行される．首都からは新たに島 $ 3 $ が到達可能になる． 2. $ 3 $ 番目の建設計画が実行される．首都からは新たに島 $ 2 $ が到達可能になる． 3. $ 5 $ 番目の建設計画が実行される．首都からは新たに島 $ 4 $ が到達可能になる． 以上より， $ D_{1, 1} = 0, D_{1, 2} = 2, D_{1, 3} = 1, D_{1, 4} = 3 $ となる． $ D_{2, 1} = 2, D_{3, 1} = 2, D_{4, 1} = 3 $ であるため，島 $ 1 $ の不便度は $ D_{1, 1} + D_{2, 1} + D_{3, 1} + D_{4, 1} = 0 + 2 + 2 + 3 = 7 $ である．また， $ D_{2, 3} = 1, D_{3, 3} = 0, D_{4, 3} = 1 $ であるため，島 $ 3 $ の不便度は $ D_{1, 3} + D_{2, 3} + D_{3, 3} + D_{4, 3} = 1 + 1 + 0 + 1 = 3 $ である． この入力例は小課題 $ 1, 2, 6 $ の制約を満たす． --- ### Sample Explanation 2 この入力例は小課題 $ 1, 2, 4, 6 $ の制約を満たす． --- ### Sample Explanation 3 この入力例は小課題 $ 1, 2, 5, 6 $ の制約を満たす． ### Constraints - $ 2 \leqq N \leqq 300\,000 $ ． - $ 1 \leqq M \leqq 600\,000 $ ． - $ 1 \leqq Q \leqq N $ ． - $ 1 \leqq A_j < B_j \leqq N $ ( $ 1 \leqq j \leqq M $ )． - すべての建設計画を実行した場合において，すべての島がいくつかの橋によって互いに到達可能になる． - $ 1 \leqq C_j \leqq 10^9 $ ( $ 1 \leqq j \leqq M $ )． - $ C_1, C_2,\ldots,C_M $ は相異なる． - $ 1 \leqq X_k\leqq N $ ( $ 1 \leqq k \leqq Q $ )． - $ X_1, X_2, \ldots, X_Q $ は相異なる． - 入力される値はすべて整数である．