← 返回题目列表

AtCoder · joi2026final_k

K. JOI王国3的节日

中文机器翻译题面 查看原题

分数: 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).
  • 给定值均为整数。

子任务

  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 (1 \leq k \leq Q).
  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 (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 点)没有额外的限制。

示例输入 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.