← 返回题目列表

AtCoder · pakencamp_2020_day2_g

G. 旅行者规划问题

中文机器翻译题面 查看原题
配点 : 800 点

問題文

企鹅人厌倦了写题,所以他决定前往帕肯王国。

帕肯王国是 N 城市 1,\ 2,\ \ldots,\ N 和 N-1 由一条主干道组成。i 真正的道路是城市 u_i 和城市 v_i 双向绑扎,长度为 w_i 。您可以使用多条道路从任何城市前往任何城市。

企鹅人简介是一座城市 在 1 留在K 我试图通过重复“使用多条道路从当前城市移动到另一个城市”的动作来旅行。多次访问同一个城市是可以的,但由于企鹅人不喜欢步行,所以他们希望以最小化总步行距离的方式旅行。

顺便说一句,旅行时经常会发生意外。所以企鹅人 我决定提前回答以下关于i=1,\ 2,\ldots,\ Q 的问题。

  • r_i 如果主干道无法通行,出行次数 定义 K 输出为 k_i 时,行驶总距离的最小值是多少?
回答所有这些问题对于企鹅人来说太困难了。请为他解答所有这些问题。


制約

  • 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 请输出问题的答案。

在每个问题中,企鹅人 如果您无法从 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 约束。

作者: 企鹅人