G - 旅人計画問題 Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 800 点

問題文

penguinman は作問作業に疲れたため、パ研王国を旅することにしました。

パ研王国は N 個の都市 1,\ 2,\ \ldots,\ N と N-1 本の道路からなります。i 本目の道路は都市 u_i と都市 v_i を双方向に結んでいて、長さは w_i です。任意の都市から任意の都市まで、いくつかの道路を用いることで移動することができます。

はじめ penguinman は都市 1 にいて、K 回に渡って「今いる都市からいくつかの道路を使って他の都市へ移動する」という行動を繰り返すことで旅をしようとしています。同じ都市を複数回訪れても構いませんが、penguinman は歩くのが嫌いなため、歩く距離の合計が最小になるように旅をしたいです。

ところで、旅にはアクシデントがつきものです。そこで penguinman は、i=1,\ 2,\ldots,\ Q について以下の質問に事前に答えておくことにしました。

  • r_i 本目の道路が通れなくなったとして、移動回数 K を k_i と定めた時の移動距離の合計の最小値はいくつか。
これらの質問全てに答え切ることは、penguinman には難しすぎました。彼の代わりにこれらの質問全てに答えてあげてください。

制約

  • 1\leq N,\ Q\leq10^5
  • 1\leq u_i,\ v_i\leq N
  • u_i≠v_i
  • 1\leq w_i\leq 10^9
  • 1\leq r_i\leq N-1
  • 1\leq k_i\leq10^9
  • 任意の都市から任意の都市までいくつかの道路を用いることで移動できる
  • 入力は全て整数

小課題

  1. (200 点) N\leq2000,\ Q\leq2000
  2. (200 点) k_i は一定
  3. (200 点) N\leq k_i
  4. (200 点) 追加の制約はない。

入力

入力は以下の形式で標準入力から与えられます。

\(N\) \(Q\)
\(u_1\) \(v_1\) \(w_1\)
\(u_2\) \(v_2\) \(w_2\)
\(︙\)
\(u_{N-1}\) \(v_{N-1}\) \(w_{N-1}\)
\(r_1\) \(k_1\)
\(r_2\) \(k_2\)
\(︙\)
\(r_Q\) \(k_Q\)

出力

i 行に渡って出力してください。i 行目には i 個目の質問への答えを出力してください。

それぞれの質問において、penguinman が都市 1 から任意の他の都市へ移動できない場合は -1 を、移動出来る場合は移動距離の合計の最小値を出力してください。

入力例1

5 8
5 1 5
4 5 2
2 5 4
3 5 2
3 2
4 8
2 4
3 8
4 3
1 8
3 10
2 1

出力例1

7
19
11
19
9
-1
23
5

このサンプルは小課題 1,\ 4 の制約を満たします。

Writer : penguinman