AT_pakencamp_2025_day2_d Ice Melting

パケン王国のパケン雪原に洞窟があり、洞窟には $ 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 $ における氷の大きさの和を求めよ。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ A_1 $ $ A_2 $ $ \dots $ $ A_N $ $ u_1 $ $ v_1 $ $ c_1 $ $ u_2 $ $ v_2 $ $ c_2 $ $ \vdots $ $ u_{N-1} $ $ v_{N-1} $ $ c_{N-1} $ $ Q $ $ a_1 $ $ b_1 $ $ t_1 $ $ a_2 $ $ b_2 $ $ t_2 $ $ \vdots $ $ a_Q $ $ b_Q $ $ t_Q $

$ Q $ 行出力せよ。 $ i $ 行目には、 $ i $ 個目の質問に対する答えを整数で出力せよ。

### 小課題 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 $ 点) 追加の制約はない。 ### Sample Explanation 1 時刻 $ 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 $ が答えとなります。 ### Constraints - $ 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} $ - 任意の部屋について、いくつかの通路を通ることで他のすべての部屋に到達できる - 入力はすべて整数である