問題一覧 > 通常問題

No.1094 木登り / Climbing tree

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 39
作問者 : nullnull / テスター : butsurizukibutsurizuki
0 ProblemId : 4567 / 出題時の順位表
問題文最終更新日: 2020-06-24 01:32:53

問題文

$N$ 頂点の重み付き無向木が与えられます。$i(1 \le i \le N - 1)$ 番目の辺は頂点 $a_i$ と頂点 $b_i$ をコスト $c_i$ で結びます。
$Q$ 個の質問に対して、$j(1 \le j \le Q)$ 番目の質問では頂点 $s_j$ から頂点 $t_j$ までの最小コストを答えてください。

入力

$N$
$a_1\ b_1\ c_1$
$a_2\ b_2\ c_2$
$\dots$
$a_{N-1}\ b_{N-1}\ c_{N-1}$
$Q$
$s_1\ t_1$
$s_2\ t_2$
$\dots$
$s_Q\ t_Q$

$1 \le N, Q \le 2 \times 10^5$
$a_i, b_i, c_i$ は頂点 $a_i$ と頂点 $b_i$ をコスト $c_i$ で結ぶ辺があることを表す。
$1 \le a_i, b_i, s_j, t_j \le N$
$1 \le c_i \le 10^4$
入力はすべて整数。
入力は木

出力

改行区切りで $Q$ 行にわたって答えを出力せよ。最後に改行せよ。

サンプル

サンプル1
入力
5
1 2 1
2 3 10
1 4 100
2 5 1000
6
1 2
1 5
2 4
1 4
5 3
1 1
出力
1
1001
101
100
1010
0

出典

YSF Beginner Contest: G - 木登り / Climbing tree
writer: null
tester: butsuri_0523
HackerRank の規約に基づいて移植されました。一部サイトの都合などで改変したところがあります。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。