AT_pakencamp_2019_day4_f イーハチはやる

Pakenomy 公司由 $N$ 个房间和 $N-1$ 条走廊组成.我们为房间编号$1 \sim N$，走廊编号 $1 \sim N-1$。走廊 $i$ 将房间 $A_i$ 和房间 $B_i$ 双向连接。通过几条走廊，可以在任意两个房间之间移动。 Pakenomy 公司管理着很多怪物。一旦发生紧急情况，这些怪物就会侵入走廊。Iihachi 是负责镇压骚动的职员。但他想事先调查一下这些行为。 当 Iihachi 通过走廊 $e$ 时，体力会减少 $C_e$。当体力小于等于 $0$ ，就会“复苏”，体力会变成 $K$。 题目有 $Q$ 次询问，第 $i$ 个问题为： - 当 Iihachi 初始以体力 $K$ 的状态，从房间 $S_i$ 通过走廊到房间 $T_i$ 的途中，最少“复苏”几次。

第一行读入两个正整数 $N,K$。 接下来 $N-1$ 行，每行读入三个正整数 $A_i,B_i,C_i$。 接下来一行，读入一个正整数 $Q$。 接下来 $Q$ 行，每行读入两个正整数 $S_i,T_i$。

输出 $Q$ 行，第 $i$ 行输出第 $i$ 个问题的答案。

本题采用捆绑测试。 - Subtask 1(5 pts) 满足 $ N=2,\ Q=1 $。 - Subtask 2(18 pts) 满足 $ N\ \leq\ 4000,\ Q\ \leq\ 4000 $。 - Subtask 3(12 pts) 满足 $ N\ \leq\ 4000 $。 - Subtask 4(33 pts) 对于任意 $i（1\leq i\leq N-1）$，满足$A_i=i$ 及 $B_i=i+1$。 - Subtask 5(32 pts) 无附加条件。 对于 $100\%$ 的数据，保证 - 输入均为整数 - $ 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) $ - 通过几条走廊，可以在任意两个房间之间移动 - $ 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) $ ### 样例解释 对于样例一： 由房间 $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$。 对于样例二，每次经过走廊都会“复苏”。 @[lihl](https://www.luogu.com.cn/user/711887) 提供翻译。