問題一覧 > 通常問題

No.1212 Second Path

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 21
作問者 : penguinmanpenguinman / テスター : ThistleThistle
2 ProblemId : 4706 / 出題時の順位表
問題文最終更新日: 2020-09-18 22:35:16

問題文

Penguinman は木で遊ぶのが大好きです。

ここに $N$ 頂点の木があります。
$i$ 番目の辺は頂点 $u_i$ と頂点 $v_i$ を双方向に結び、長さは $w_i$ です。

以下のクエリが $Q$ 個与えられるので、順に処理してください。
クエリ:
  頂点 $x$ で始まり頂点 $y$ で終わる、 以下の条件を満たすような、要素の重複を許す頂点列の中で $2$ 番目に長さが短いものの長さを求めて出力してください。
  ただし、そのような頂点列が存在しない場合は代わりに $-1$ を出力してください。
条件:

  1. $i$ 番目の頂点と $i+1$ 番目の頂点が直接辺で結ばれている$(1≤i≤($頂点列のサイズ$-1))$

  2. $i$ 番目の頂点と $i+1$ 番目の頂点を結ぶ辺のうち、同じものは $2$ 度までしか現れない。


ただし、頂点列の長さとは全ての $i(1≤i≤($頂点列のサイズ$-1))$における $i$ 番目の頂点と $i+1$ 番目の頂点を結ぶ辺の長さの総和のことを指します。
また、長さが同じでも頂点列として異なれば区別することとします。

入力

$N$
$u_1\ v_1\ w_i$
:
$u_{N-1}\ v_{N-1}\ w_{N-1}$
$Q$
$x_1\ y_1$
:
$x_Q\ y_Q$

便宜上 $i$ 番目のクエリにおける $x,y$ をそれぞれ $x_i,y_i$ としています。
また、以下の制約を満たすことが保証されます。
・$2≤N≤10^5$
・$1≤Q≤10^5$
・$1≤u_i,v_i≤N(1≤i≤N-1)$
・$1≤w_i≤10^9(1≤i≤N-1)$
・$1≤x_i,y_i≤N(1≤i≤Q)$
・$u_i≠v_i(1≤i≤N-1)$
・$x_i≠y_i(1≤i≤Q)$
・与えられるグラフは木
・入力は全て整数

出力

$i$ 行目には $i$ 番目のクエリに対する答えを出力してください。

サンプル

サンプル1
入力
3
1 2 3
2 3 4
2
1 2
1 3
出力
11
-1

$1$ 個目のクエリでは、{1,2,3,1}$\{1,2,3,2\}$ (13:53 問題文修正) という頂点列の長さが $2$ 番目に長くなります短くなります。(13:53 問題文修正) これの長さは $11$ なので、それを出力します。
長さ自体は $\{1,2,1,2\}$ の方が短いですが、これは同じ辺を $3$ 回通っていて②の条件を満たしません。
$2$ 個目のクエリでは、条件を満たす頂点列が $1$ 通りしか存在しません。よって $-1$ を出力します。

サンプル2
入力
5
1 4 10
2 3 100
1 2 38
1 5 2
4
1 2
2 3
3 4
1 4
出力
42
176
152
14

サンプル3
入力
6
1 3 19
1 2 20
1 4 1
5 1 10
4 6 8
5
1 2
3 4
5 3
6 2
3 1
出力
22
36
31
49
21

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