分数: 100 点
问题陈述
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 is 相邻 前往城市 v 如果这两个城市有高速公路直接连接。 当一座城市点燃圣火的那一刻,一支游行队伍将从这座城市出发,前往每一个邻近的城市,所花的时间相当于相应高速公路的行驶时间。 准确地说,对于两个相邻的城市 v 和 u,来自城市的游行 v 到达城市 u 时间 t+d,其中 t 是城市大锅的时间 v 被点燃,并且 d 是连接城市的高速公路的行驶时间 v 和 u.
有些城市在节日开始时就点燃大锅,而其他城市只有在节日足够热后才会点燃。 让时间 0 是节日的开始。 对于城市 i 谁的受欢迎程度是 c,城市的时间 i 点燃其大锅确定如下:
- If c = 0, 城市 i 及时点燃它的大锅 0.
- If c \geq 1, 城市 i 当从邻近城市到达的游行队伍数量达到至少 c。 如果这永远不会发生,城市 i 永远不会点燃它的大锅。
K先生将留在JOI Kingdom。 在他逗留期间,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。假设此时开始有节日,则必须判断是否 {city \nolinebreak 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)
(查询 k) 代表事件的详细信息 k (1 \leq k \leq Q)。 在(查询 k),写入空格分隔的整数。 让 P_k 是第一个整数。 P_k is 1, 2,或 3,表示事件类型 k。 然后(查询 k) 含义如下:
- If P_k = 1,还有两个整数 V_k, X_k 按此顺序写入。 这意味着城市的人气 V_k 更改为 X_k.
- If P_k = 2,还有两个整数 E_k, X_k 按此顺序写入。 这意味着高速公路的行驶时间 E_k 更改为 X_k.
- If P_k = 3,多了一个整数 V_k 写的。 这意味着K先生访问城市 V_k 并且,假设节日此时开始,您必须确定城市大锅的时间 V_k 被点燃。
输出
对于标准输出,为每个事件在一行中输出以下内容 k (1 \leq k \leq Q) 与 P_k = 3,按升序排列 k.
- 如果K先生访问的城市会点燃大锅,输出大锅被点燃的时间。
- 否则,输出
-1.
约束
- 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.
- If P_k = 1,我们有 1 \leq V_k \leq N, 0 \leq X_k \leq N (1 \leq k \leq Q).
- If P_k = 2,我们有 1 \leq E_k \leq N-1, 1 \leq X_k \leq 1\,000\,000 (1 \leq k \leq Q).
- If P_k = 3,我们有 1 \leq V_k \leq N (1 \leq k \leq Q).
- 给定值均为整数。
子任务
- (6 点) N \leq 2\,000, Q \leq 2\,000.
- (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).
- (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 (1 \leq k \leq Q).
- (25 点) P_k \neq 1。 如果 P_k = 3,我们有 V_k = 1 (1 \leq k \leq Q).
- (12 点)如果 P_k = 3,我们有 V_k = 1 (1 \leq k \leq Q).
- (22 点) P_k \neq 1 (1 \leq k \leq Q).
- (14 点)没有额外的限制。
示例输入 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
示例输出 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
示例输出 2
30 20 10 30 -1
此示例输入满足子任务的约束 1,2,5,7.