AdditionalFile5673.zip

#5673. 「JOI 2026 Final Day4」JOI 国的祭典情况 3

标签: 传统 | 时间限制: 4000 ms | 内存限制: 1024 MiB |

题目描述

题目译自 JOI 2026 Final Day4 T2 「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 国的祭典中，有先点燃圣火台，再以此为信号让游行队伍从城市出发的传统。

当城市 $v$ 和城市 $u$ 有国道直接相连时，称城市 $u$ 与城市 $v$ 相邻。当某个城市的圣火台被点燃时，该城市会向每个相邻城市各派出一支游行队伍。游行队伍在国道上行进的时间与其对应的行驶时间相同，随后到达对面的城市。也就是说，对于互相相邻的城市 $v$ 和 $u$，如果城市 $v$ 的圣火台在时刻 $t$ 被点燃，且连接城市 $v, u$ 的国道行驶时间为 $d$，那么从城市 $v$ 出发的游行队伍到达城市 $u$ 的时刻为 $t+d$。

有些城市会在祭典开始的一瞬间点火，而有些城市则会在祭典气氛达到高潮时点火。设定祭典开始的时刻为时刻 $0$。设城市 $i$ 的人气度为 $c$，该城市圣火台的点火时刻按如下规则确定：

• 如果 $c=0$，则在时刻 $0$ 点火。
• 如果 $c \geq 1$，则在来自相邻城市的游行队伍到达数量首次达到 $c$ 个或以上的时刻点火。如果该情况从未发生，则不点火。

现在，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$。此时需要判定：如果祭典在此刻开始，城市 $V_k$ 的圣火台是否会被点燃。如果会被点燃，则求出点火时刻。

给定 JOI 国的结构、城市人气度、国道行驶时间以及在留期间发生的事件信息，请编写一个程序，计算在类型 3 事件中，K 理事长所在城市的圣火台点火的时刻。

输入格式

第一行包含一个整数 $N$。

接下来的 $N-1$ 行，其中第 $i$ 行包含四个整数 $A_i, B_i, D_i$。

接下来的 $N$ 行，其中第 $i$ 行包含一个整数 $C_i$。

接下来一行包含一个整数 $Q$。

接下来 $Q$ 行，第 $k$ $(1 \leq k \leq Q)$ 行表示第 $k$ 个询问，包含若干个由空格分隔的整数。其中第一个整数是代表事件类型的 $1, 2, 3$ 之一。设其为 $P_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 \leq k \leq Q)$，按 $k$ 的升序分行输出结果。如果 K 理事长所在城市的圣火台会被点燃，则输出点火时刻；如果无法点燃，则输出 $-1$。

样例 1

输入

7
1 2 30
2 3 30
1 4 70
2 5 20
1 6 10
2 7 50
2
3
0
0
0
1
0
8
3 1
1 6 0
3 1
2 6 10
3 1
1 2 7
1 6 7
3 1

输出

80
70
60
-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

输入

6
1 2 10
1 3 30
1 4 50
1 5 30
1 6 10
2
0
0
0
0
1
10
3 1
2 3 20
3 1
1 6 0
3 1
1 1 4
3 1
1 2 6
1 3 6
3 1

输出

30
20
10
30
-1

该样例满足子任务 $1, 2, 5, 7$ 的限制。

数据范围与提示

对于所有输入数据，满足：

• $2 \leq N \leq 150000$。
• $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 1000000$ $(1 \leq j \leq N-1)$。
• 任意两个城市之间都可通过国道连通。
• $1 \leq Q \leq 150000$。
• 当 $P_k=1$ 时，$1 \leq V_k \leq N, 0 \leq X_k \leq N$ $(1 \leq k \leq Q)$。
• 当 $P_k=2$ 时，$1 \leq E_k \leq N-1, 1 \leq X_k \leq 1000000$ $(1 \leq k \leq Q)$。
• 当 $P_k=3$ 时，$1 \leq V_k \leq N$ $(1 \leq k \leq Q)$。
• 所有输入的值均为整数。

详细子任务附加限制及分值如下表所示。

子任务	分值	附加限制
$1$	$6$	$N \leq 2000, Q \leq 2000$
$2$	$7$	$A_j=1, B_j=j+1$ $(1 \leq j \leq N-1)$。当 $P_k=3$ 时，$V_k=1$ $(1 \leq k \leq Q)$。
$3$	$14$	$N-1$ 是 $3$ 的倍数。$A_j=\left((j-1) \bmod \frac{N-1}{3}\right)+1, B_j=j+1$ $(1 \leq j \leq N-1)$。当 $P_k=3$ 时，$V_k=1$ $(1 \leq k \leq Q)$。
$4$	$25$	$P_k \neq 1$。当 $P_k=3$ 时，$V_k=1$ $(1 \leq k \leq Q)$。
$5$	$12$	当 $P_k=3$ 时，$V_k=1$ $(1 \leq k \leq Q)$。
$6$	$22$	$P_k \neq 1$ $(1 \leq k \leq Q)$。
$7$	$14$	无附加限制。