AT_joi2026final_k 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 王国的每个城市都有一个大锅。
在节日期间，每个城市会点燃自己大锅，并由此向相邻城市派出巡游队伍。
如果城市 $u$ 和城市 $v$ 通过高速公路直接相连，则称这两个城市是相邻的。
在城市点燃大锅的那一刻，它会向每个相邻城市各派出一队巡游队伍，花费与该高速公路通行时间相同的时间抵达对方城市。
更具体地说，若相邻的城市 $v$ 和 $u$，当城市 $v$ 的大锅在时刻 $t$ 被点燃时，来自 $v$ 的巡游队伍会在 $t+d$ 时刻到达 $u$，其中 $d$ 是连接 $v$ 和 $u$ 的高速公路通行时间。
有些城市在节日开始的瞬间就点燃大锅，而其他城市会在节日气氛足够热烈的时候才点燃。
令时刻 $0$ 为节日开始。
对于人气度为 $c$ 的城市 $i$，其点燃大锅的时刻满足以下规则：
- 若 $c=0$，城市 $i$ 会在时刻 $0$ 点燃大锅。
- 若 $c\geq 1$，城市 $i$ 会在相邻城市中来自的巡游队伍数量至少到达 $c$ 时点燃大锅。如果这种情况永远不会发生，则城市 $i$ 永远不会点燃大锅。
K 先生会来到 JOI 王国。
在他停留期间，JOI 王国会发生 $Q$ 个与节日相关的事件。
这些事件按时间先后编号为 $1$ 到 $Q$。
第 $k$ 个事件（$1 \leq k \leq Q$）有以下三种类型之一：
- 类型 $1$：城市 $V_k$ 的人气度变为 $X_k$。
- 类型 $2$：第 $E_k$ 条高速公路的通行时间变为 $X_k$。
- 类型 $3$：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$，表示事件的类型。之后的内容如下：
- 若 $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$，你需要判断此时节日开始后该城市点燃大锅的时刻。
输出格式
对于每一个 $P_k = 3$ 的事件，依次按事件编号输出一行。
- 如果该城市会点燃大锅，则输出其点燃大锅的时刻。
- 否则，输出 `-1`。
---
说明/提示
### 子任务
1.（$6$ 分）$N \leq 2\,000$，$Q \leq 2\,000$。
2.（$7$ 分）$A_j=1$，$B_j=j+1$（$1 \leq j \leq N-1$）。若 $P_k=3$，则 $V_k=1$。
3.（$14$ 分）$N-1$ 可被 $3$ 整除，$A_j = ((j-1) \bmod \frac{N-1}{3})+1$，$B_j = j+1$（$1 \leq j \leq N-1$）。若 $P_k=3$，则 $V_k=1$。
4.（$25$ 分）$P_k \neq 1$。若 $P_k=3$，则 $V_k=1$。
5.（$12$ 分）若 $P_k=3$，则 $V_k=1$。
6.（$22$ 分）$P_k \neq 1$（$1 \leq k \leq Q$）。
7.（$14$ 分）无其他额外限制。
---
### 样例解释 1
对于事件 $1$ 中的节日，各城市点燃大锅的时刻如下：
- 时间 $0$，城市 $3,4,5,7$ 点燃大锅。
- 时间 $50$，城市 $2$ 点燃大锅。此时已收到来自城市 $3,5,7$ 的巡游队伍。
- 时间 $80$，城市 $1$ 点燃大锅。此时已收到来自城市 $2,4$ 的巡游队伍。
- 时间 $90$，城市 $6$ 点燃大锅。此时已收到来自城市 $1$ 的巡游队伍。
由于城市 $1$ 会在时刻 $80$ 点燃大锅，所以输出 $80$。
对于事件 $3$ 的节日，各城市点燃大锅的时刻如下：
- 时间 $0$，城市 $3,4,5,6,7$ 点燃大锅。
- 时间 $50$，城市 $2$ 点燃大锅。此时已收到来自城市 $3,5,7$ 的巡游队伍。
- 时间 $70$，城市 $1$ 点燃大锅。此时已收到来自城市 $4,6$ 的巡游队伍。
由于城市 $1$ 会在时刻 $70$ 点燃大锅，所以输出 $70$。
对于事件 $5$ 的节日，各城市点燃大锅的时刻如下：
- 时间 $0$，城市 $3,4,5,6,7$ 点燃大锅。
- 时间 $30$，城市 $2$ 点燃大锅。此时已收到来自城市 $3,5,7$ 的巡游队伍。
- 时间 $60$，城市 $1$ 点燃大锅。此时已收到来自城市 $2,6$ 的巡游队伍。
由于城市 $1$ 会在时刻 $60$ 点燃大锅，所以输出 $60$。
对于事件 $8$ 的节日，时间 $0$，只有城市 $3,4,5,7$ 点燃大锅。
城市 $1,2,6$ 永远不会点燃大锅。因为城市 $1$ 永远不会点燃大锅，所以输出 `-1`。
此输入样例符合子任务 $1,3,5,7$ 的约束。
---
### 样例解释 2
此输入样例符合子任务 $1,2,5,7$ 的约束。
### 数据范围
- $2 \leq N \leq 150\,000$。
- $0 \leq C_i \leq N$（$1 \leq i \leq N$）。
- $1 \leq A_j < B_j \leq N$（$1 \leq j \leq N-1$）。
- $1 \leq D_j \leq 1\,000\,000$（$1 \leq j \leq N-1$）。
- 高速公路构成联通图。
- $1 \leq Q \leq 150\,000$。
- 若 $P_k = 1$，$1 \leq V_k \leq N$，$0 \leq X_k \leq N$。
- 若 $P_k = 2$，$1 \leq E_k \leq N-1$，$1 \leq X_k \leq 1\,000\,000$。
- 若 $P_k = 3$，$1 \leq V_k \leq N$。
- 输入数据均为整数。
由 ChatGPT 5 翻译