問題一覧 > 通常問題

No.1212 Second Path

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 24
作問者 : penguinmanpenguinman / テスター : ThistleThistle
3 ProblemId : 4706 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-01-17 05:18:48

問題文

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もしくは右上の雲マークをクリックしてアカウントを作成してください。