問題文

パケン王国のパケン雪原に洞窟があり、洞窟には N 個の部屋があります。また、部屋 i には初期状態で大きさ A_i の氷があります。 また、洞窟には部屋と部屋の間を双方向に結ぶ通路が N-1 本あり、i 本目の通路は部屋 u_i と部屋 v_i を結んでいて、c_i=1 のときに限り i 本目の通路に熱源が置かれています。ここで、任意の部屋について、いくつかの通路を通ることで他のすべての部屋に到達できることが保証されます。

時刻 0 から、部屋 i の氷は、以下の条件を満たしているときに限り単位時間あたり 1 の速度で大きさが減少します。ただし、氷の大きさが 0 より小さくなることはないものとします。

• 部屋 i から、大きさが 0 より大きい氷がある他の部屋を通らずに、いずれかの熱源が置かれた通路に到達することができる。

Q 個の質問が与えられるので、それぞれについて解答してください。i 個目の質問は以下のようなものです。

• 部屋 a_i から部屋 b_i まで移動する際、通る通路の本数を最小化するような経路を考える（このような経路は一意に定まることが証明可能である）。このとき、移動の途中で通る部屋すべて（部屋 a_i, b_i にある氷も含める）に対する、時刻 t_i における氷の大きさの和を求めよ。

制約

• 2 \le N \le 200000
• 1 \le Q \le 200000
• 1 \le A_i \le 10^9
• 1 \le u_i, v_i \le N
• u_i \neq v_i
• c_i \in \{0, 1\}
• c_i = 1 となる i が少なくとも 1 つ存在する
• 1 \le a_i, b_i \le N
• 0 \le t_i \le 10^{10}
• 任意の部屋について、いくつかの通路を通ることで他のすべての部屋に到達できる
• 入力はすべて整数である

小課題

1. (7 点) N, Q \leq 1000,u_i = i, v_i = i+1\ (1 \le i \le N-1)
2. (8 点) N, Q \leq 1000
3. (7 点) u_i = i, v_i = i+1\ (1 \le i \le N-1)、すべての 1 \le i, j \le Q について t_i = t_j である。
4. (14 点) u_i = i, v_i = i+1\ (1 \le i \le N-1)、すべての 1 \le i \le Q について、 (a_i, b_i) = (1, N) である。
5. (28 点) u_i = i, v_i = i+1\ (1 \le i \le N-1)
6. (6 点) N, Q \leq 100000、すべての 1 \le i, j \le Q について t_i = t_j である。
7. (15 点) N, Q \leq 100000
8. (15 点) 追加の制約はない。

入力例 1

3
10 20 30
1 2 1
2 3 0
2
1 3 5
2 3 10

出力例 1

50
40

時刻 0 の時点では、部屋 1 と部屋 2 は熱源の置かれた通路に（他の氷がある部屋を通らずに）到達できるため、氷が溶け始めます。部屋 3 は部屋 2 の氷が邪魔をして熱源に到達できないため、まだ氷は溶けません。

• 1 個目の質問は、時刻 5 の状態に関するものです。部屋 1 の氷の大きさは 10 - 5 = 5、部屋 2 の氷の大きさは 20 - 5 = 15 となっています。部屋 3 の氷はまだ溶け始めていないため大きさは 30 です。求めるべき経路上にある部屋は 1, 2, 3 なので、和である 5 + 15 + 30 = 50 が答えとなります。
• 2 個目の質問は、時刻 10 の状態に関するものです。部屋 1 の氷は完全に溶けて大きさが 0 になり、部屋 2 の氷の大きさは 20 - 10 = 10 となっています。求めるべき経路上の部屋は 2, 3 なので、和である 10 + 30 = 40 が答えとなります。