AT_pakencamp_2019_day4_f イーハチはやる

[problemUrl]: https://atcoder.jp/contests/pakencamp-2019-day4/tasks/pakencamp_2019_day4_f Pakenomy 社は $ N $ 個の部屋と $ N-1 $ 本の廊下から成り，部屋は $ 1 $ から $ N $ の，廊下は $ 1 $ から $ N-1 $ の番号がついています． 廊下 $ i $ は部屋 $ A_i $ と 部屋 $ B_i $ を双方向に結んでいます．廊下を何本か通ることで任意の $ 2 $ 部屋の間を移動できるようになっています． Pakenomy 社では多くの怪物を管理しており，緊急事態が起こるとそれらが廊下に侵入することが想定されます．イーハチはこのような状況において騒動の鎮圧を担当する職員ですが，前もって振る舞いを調べようと考えています． イーハチが廊下 $ e $ を通るとき，体力が $ C_e $ 減ります．ここで体力が $ 0 $ 以下になった場合，「蘇生」イベントが起き，体力が $ K $ になります． $ Q $ 個の質問が与えられ，$ i $ 番目の質問は以下の通りです． - イーハチがはじめ体力 $ K $ の状態で部屋 $ S_i $ にいて，廊下を何回か通って部屋 $ T_i $ に移動するとき，「蘇生」イベントが起こる回数は最小で何回か？ あなたの仕事は，$ Q $ 個の質問全てに答えることです．

入力は以下の形式で標準入力から与えられます． > $ 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 $ 番目の質問に対する答えを出力してください．

### 制約 - 入力はすべて整数 - $ 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 点) 追加の制約はない． ### Sample Explanation 1 部屋 $ 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 $ になる． ### Sample Explanation 2 廊下を通るたびに蘇生することになります．