配点: 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)
部分点
该问题分为多个子任务,如果您正确回答了该子任务的所有测试用例,则视为您已正确回答了“该子任务”。
提交的源代码的分数是您正确回答的子作业分数的总和。
- (5 点) N=2, Q=1 满意。
- (18 点) N \leq 4000, Q \leq 4000 满意。
- (12 点) N \leq 4000 满意。
- (33 分) 任意 关于 i\ (1 \leq i \leq N-1) ,A_i=i 和 B_i=i+1 满意。
- (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