問題一覧 > 通常問題

No.1212 Second Path

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

問題文

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

ここに N 頂点の木があります。i 番目の辺は頂点 ui と頂点 vi を双方向に結び、長さは wi です。以下のクエリが Q 個与えられるので、順に処理してください。

  • 頂点 x で始まって頂点 y で終わり、また以下の条件を共に満たすような、要素の重複を許す頂点列の中で 2 番目に長さが短いものの長さを求めて出力してください。そのような頂点列が存在しない場合は代わりに 1 を出力してください。

    1. i 番目の頂点と i+1 番目の頂点が直接辺で結ばれている (1i(頂点列のサイズ1))
    2. i 番目の頂点と i+1 番目の頂点を結ぶ辺のうち、同じものは 2 度までしか現れない。
ここで、頂点列の長さとは全ての i(1i(頂点列のサイズ1))における i 番目の頂点と i+1 番目の頂点を結ぶ辺の長さの総和のことを指します。

また、長さが同じでも頂点列として異なれば区別することとします。

入力

N
u1 v1 wi
:
uN1 vN1 wN1
Q
x1 y1

xQ yQ

便宜上 i 番目のクエリにおける x,y をそれぞれ xi,yi としています。

入力は以下の制約を満たすことが保証されます。

  • 2N105
  • 1Q105
  • 1ui,viN(1iN1)
  • 1wi109(1iN1)
  • 1xi,yiN(1iQ)
  • uivi(1iN1)
  • xiyi(1iQ)
  • 与えられるグラフは木
  • 入力は全て整数

出力

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