P15949 [JOI Final 2026] JOI 国的节日 3 / Festivals in JOI Kingdom 3

JOI 国由 $N$ 座城市和 $N-1$ 条高速公路组成。这些城市的编号为 $1$ 到 $N$，高速公路的编号为 $1$ 到 $N-1$。通过穿过若干条高速公路，可以从任何一座城市到达任何其他城市。 每座城市都有一个**热度**，用一个非负整数表示。城市 $i$（$1 \leq i \leq N$）的初始热度为 $C_i$。每条高速公路都有一个**通行时间**，用一个正整数表示。高速公路 $j$（$1 \leq j \leq N-1$）连接着城市 $A_j$ 和城市 $B_j$，其初始通行时间为 $D_j$。 JOI 国的每座城市都有一个圣火盆。JOI 国保持着一个传统，即在节日里，各个城市会点燃它们的圣火盆，这些点火仪式标志着游行队伍从这些城市出发。 如果两座城市由一条高速公路直接相连，则城市 $u$ 与城市 $v$ 是**相邻**的。在某座城市点燃其圣火盆的准确瞬间，将有一支游行队伍从该城市出发前往其每个相邻的城市，所花费的时间等于对应高速公路的通行时间。准确地说，对于两个相邻的城市 $v$ 和 $u$，从城市 $v$ 出发的游行队伍在时间 $t + d$ 到达城市 $u$，其中 $t$ 是城市 $v$ 的圣火盆被点燃的时间，$d$ 是连接城市 $v$ 和 $u$ 的高速公路的通行时间。 有些城市在节日开始的瞬间就会点燃它们的圣火盆，而另一些城市则只有在节日气氛足够热烈后才会这样做。令时间 $0$ 为节日的开始。对于热度为 $c$ 的城市 $i$，城市 $i$ 点燃其圣火盆的时间按如下方式确定： - 如果 $c = 0$，城市 $i$ 在时间 $0$ 点燃其圣火盆。 - 如果 $c \geq 1$，当从相邻城市到达的游行队伍数量至少达到 $c$ 时，城市 $i$ 就会点燃其圣火盆。如果这种情况永远没有发生，城市 $i$ 就永远不会点燃其圣火盆。 K 先生将在 JOI 国逗留。在他逗留期间，JOI 国将发生 $Q$ 个与其节日相关的事件。这些事件按照发生时间从早到晚编号为 $1$ 到 $Q$。 事件 $k$（$1 \leq k \leq Q$）是以下 $3$ 种类型之一： - 类型 $1$：城市 $V_k$ 的热度变为 $X_k$。 - 类型 $2$：高速公路 $E_k$ 的通行时间变为 $X_k$。 - 类型 $3$：K 先生访问城市 $V_k$。假设一个节日在此刻开始，你必须确定城市 $V_k$ 是否会点燃其圣火盆，如果会，计算出圣火盆被点燃的时间。 编写一个程序，在给定 JOI 国的结构、每座城市的热度、每条高速公路的通行时间以及事件详情的情况下，对于每个类型 $3$ 的事件，确定 K 先生访问的城市何时点燃其圣火盆。

从标准输入读取以下数据。 > $N$\ > $A_1\ B_1\ D_1$\ > $\vdots$\ > $A_{N-1}\ B_{N-1}\ D_{N-1}$\ > $C_1$\ > $\vdots$\ > $C_N$\ > $Q$\ > (Query $1$)\ > $\vdots$\ > (Query $Q$) (Query $k$) 表示事件 $k$（$1 \leq k \leq Q$）的详情。在 (Query $k$) 中，写入了以空格分隔的整数。令 $P_k$ 为第一个整数。$P_k$ 为 $1$、$2$ 或 $3$，表示事件 $k$ 的类型。那么 (Query $k$) 的含义如下： - 如果 $P_k = 1$，则后面还按此顺序写入了两个整数 $V_k, X_k$。这意味着城市 $V_k$ 的热度变为了 $X_k$。 - 如果 $P_k = 2$，则后面还按此顺序写入了两个整数 $E_k, X_k$。这意味着高速公路 $E_k$ 的通行时间变为了 $X_k$。 - 如果 $P_k = 3$，则后面还写入了一个整数 $V_k$。这意味着 K 先生访问了城市 $V_k$，并且假设一个节日在此刻开始，你必须确定城市 $V_k$ 的圣火盆被点燃的时间。

向标准输出输出，对于每个 $P_k = 3$ 的事件 $k$（$1 \le k \le Q$），按照 $k$ 递增的顺序，每行输出以下内容： - 如果 K 先生访问的城市会点燃其圣火盆，输出该圣火盆被点燃的时间。 - 否则，输出 $\texttt{-1}$。

### 样例 1 在事件 $1$ 考虑的节日中，各城市点燃圣火盆的时间如下： - 在时间 $0$，城市 $3, 4, 5, 7$ 点燃了它们的圣火盆。 - 在时间 $50$，城市 $2$ 点燃了它的圣火盆。到那时，来自城市 $3, 5, 7$ 的游行队伍已经到达了城市 $2$。 - 在时间 $80$，城市 $1$ 点燃了它的圣火盆。到那时，来自城市 $2, 4$ 的游行队伍已经到达了城市 $1$。 - 在时间 $90$，城市 $6$ 点燃了它的圣火盆。到那时，来自城市 $1$ 的游行队伍已经到达了城市 $6$。 由于城市 $1$ 会在时间 $80$ 点燃其圣火盆，因此输出 $80$。 在事件 $3$ 考虑的节日中，各城市点燃圣火盆的时间如下： - 在时间 $0$，城市 $3, 4, 5, 6, 7$ 点燃了它们的圣火盆。 - 在时间 $50$，城市 $2$ 点燃了它的圣火盆。到那时，来自城市 $3, 5, 7$ 的游行队伍已经到达了城市 $2$。 - 在时间 $70$，城市 $1$ 点燃了它的圣火盆。到那时，来自城市 $4, 6$ 的游行队伍已经到达了城市 $1$。 由于城市 $1$ 会在时间 $70$ 点燃其圣火盆，因此输出 $70$。 在事件 $5$ 考虑的节日中，各城市点燃圣火盆的时间如下： - 在时间 $0$，城市 $3, 4, 5, 6, 7$ 点燃了它们的圣火盆。 - 在时间 $30$，城市 $2$ 点燃了它的圣火盆。到那时，来自城市 $3, 5, 7$ 的游行队伍已经到达了城市 $2$。 - 在时间 $60$，城市 $1$ 点燃了它的圣火盆。到那时，来自城市 $2, 6$ 的游行队伍已经到达了城市 $1$。 由于城市 $1$ 会在时间 $60$ 点燃其圣火盆，因此输出 $60$。 在事件 $8$ 考虑的节日中，各城市点燃圣火盆的时间如下： - 在时间 $0$，城市 $3, 4, 5, 7$ 点燃了它们的圣火盆。 城市 $1, 2, 6$ 永远不会点燃它们的圣火盆。由于城市 $1$ 永远不会点燃其圣火盆，因此输出 $-1$。 此样例输入满足子任务 $1, 3, 5, 7$ 的约束条件。 ### 样例 2 此样例输入满足子任务 $1, 2, 5, 7$ 的约束条件。 ### 约束条件 - $2 \le N \le 150000$。 - $0 \le C_i \le N$ ($1 \le i \le N$)。 - $1 \le A_j < B_j \le N$ ($1 \le j \le N-1$)。 - $1 \le D_j \le 1000000$ ($1 \le j \le N-1$)。 - 通过穿过若干条高速公路，可以从任何一座城市到达任何其他城市。 - $1 \le Q \le 150000$。 - 如果 $P_k = 1$，则有 $1 \le V_k \le N$, $0 \le X_k \le N$ ($1 \le k \le Q$)。 - 如果 $P_k = 2$，则有 $1 \le E_k \le N-1$, $1 \le X_k \le 1000000$ ($1 \le k \le Q$)。 - 如果 $P_k = 3$，则有 $1 \le V_k \le N$ ($1 \le k \le Q$)。 - 给定的值均为整数。 ### 子任务 1. (6 分) $N \le 2000$, $Q \le 2000$。 2. (7 分) $A_j = 1$, $B_j = j+1$ ($1 \le j \le N-1$)。如果 $P_k = 3$，则有 $V_k = 1$ ($1 \le k \le Q$)。 3. (14 分) $N-1$ 能被 $3$ 整除。$A_j = ((j-1) \mod \frac{N-1}{3}) + 1$, $B_j = j+1$ ($1 \le j \le N-1$)。如果 $P_k = 3$，则有 $V_k = 1$ ($1 \le k \le Q$)。 4. (25 分) $P_k \ne 1$。如果 $P_k = 3$，则有 $V_k = 1$ ($1 \le k \le Q$)。 5. (12 分) 如果 $P_k = 3$，则有 $V_k = 1$ ($1 \le k \le Q$)。 6. (22 分) $P_k \ne 1$ ($1 \le k \le Q$)。 7. (14 分) 无附加约束条件。