← 返回题目列表

AtCoder · pakencamp_2019_day4_f

F. 我八公会做的

中文机器翻译题面 查看原题

配点: 100 点

問題文

Pakenomy 是 N 房间和 N-1 房间由一条书籍走廊组成, 1 到 N ,走廊是 它的编号为 1 到 N-1 。 走廊 i 是一个房间 A_i 和房间 B_i 双向连接。通过几条走廊,你可以 2 您现在可以在房间之间移动。

帕肯诺米管理着许多怪物,预计它们会在紧急情况发生时入侵走廊。伊八是负责在这种情况下镇压骚乱的官员,但我正在考虑提前调查他的行为。

伊八在走廊里 当经过 e 时,你的体力为 C_e 将减少。这是我的体力 0 如果低于,就会发生“复活”事件,你的生命值会下降。 它变成 K 。 鉴于

Q 问题, 第i 题如下。

  • 伊八的起始体力 房间状况 K 房间状况良好 S_i 并穿过走廊几次才能到达房间。 当移动到 T_i 时,“复活”事件最少可以发生多少次?

你的工作是 目标是回答所有Q 问题。

制約

  • 输入全部为整数
  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq K \leq 10^9
  • 1 \leq A_i, B_i \leq N\ (1 \leq i \leq N-1)
  • 通过几条走廊,你可以 2 可以在房间之间移动
  • 0 \leq C_i \leq 10^9\ (1 \leq i \leq N-1)
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq S_i, T_i \leq N\ (1 \leq i \leq Q)
  • S_i \neq T_i\ (1 \leq i \leq Q)

部分点

该问题分为多个子任务,如果您正确回答了该子任务的所有测试用例,则视为您已正确回答了“该子任务”。

提交的源代码的分数是您正确回答的子作业分数的总和。

  1. (5 点) N=2, Q=1 满意。
  2. (18 点) N \leq 4000, Q \leq 4000 满意。
  3. (12 点) N \leq 4000 满意。
  4. (33 分) 任意 关于 i\ (1 \leq i \leq N-1) ,A_i=i 和 B_i=i+1 满意。
  5. (32 分) 没有额外的限制。

入力

输入是按以下格式从标准输入给出的。 请输出

N K
A_1 B_1 C_1
:
A_{N-1} B_{N-1} C_{N-1}
Q
S_1 T_1
:
S_Q T_Q

出力

Q 行。 请输出第i 在行中,i 题的答案。


入力例 1

7 5
1 2 3
1 3 10
1 4 3
2 5 1
2 6 2
5 7 1
3
3 6
4 7
7 6

出力例 1

2
1
0

部屋 3 从房间 当前往 6 时,你的体力将发生如下变化。

  • 廊下 2 通过增加体力 5 - 10 = -5 ,“复活”事件会增加你的体力。 它变成 5 。
  • 廊下 1 通过增加体力 5 - 3 = 2 。
  • 廊下 5 通过增加体力 2 - 2 = 0 ,“复活”事件会增加你的体力。 它变成 5 。

部屋 4 从房间 当前往 7 时,你的体力将发生如下变化。

  • 廊下 3 通过增加体力 5 - 3 = 2 。
  • 廊下 1 通过增加体力 2 - 3 = -1 ,“复活”事件会增加你的体力。 它变成 5 。
  • 廊下 4 通过增加体力 5 - 1 = 4 。
  • 廊下 6 通过增加体力 4 - 1 = 3 。

部屋 7 从房间 当前往 6 时,你的体力将发生如下变化。

  • 廊下 6 通过增加体力 5 - 1 = 4 。
  • 廊下 4 通过增加体力 4 - 1 = 3 。
  • 廊下 5 通过增加体力 3 - 2 = 1 。

入力例 2

7 5
1 2 30843382
1 3 31046102
1 4 31236232
2 5 31487860
2 6 32171282
5 7 33077326
3
3 6
4 7
7 6

出力例 2

3
4
3

每次穿过走廊时你都会复活。


入力例 3

20 3
18 11 2
20 9 0
2 1 2
13 8 1
12 8 1
12 4 2
6 15 0
7 16 1
3 19 1
20 5 2
16 11 0
14 2 2
16 10 0
7 2 1
12 20 2
13 19 1
1 5 1
6 17 0
17 4 2
20
1 4
8 4
3 5
11 12
14 1
9 16
6 4
20 1
6 16
4 1
19 13
20 19
18 13
9 1
4 10
7 8
18 7
18 11
7 11
1 2

出力例 3

2
1
2
2
1
2
0
1
3
2
0
1
4
1
3
3
1
0
0
0