分数: 650 点
问题陈述
有一棵树 N 顶点编号 1 to N。的 i第一条边连接顶点 a_i 和 b_i。每个顶点 i 有一个重量 W_i 和颜色 C_i \in \lbrace 0,1 \rbrace.
流程 Q 查询。查询有以下三种类型。
1 v:更改 C_v to 1 - C_v 对于顶点 v.2 v x:更改 W_v to W_v + x 对于顶点 v.3 v:让 c 是顶点的颜色 v。输出从顶点可达的所有顶点的权重之和 v 仅穿过颜色顶点 c (包括顶点 v 本身)。
约束
- 1 \leq N \leq 3 \times 10^5
- 1 \leq Q \leq 2 \times 10^5
- 1 \leq W_i \leq 10^9
- C_i \in \lbrace 0,1 \rbrace
- 1 \leq a_i \lt b_i \leq N
- 输入图是一棵树。
- 1 \leq v \leq N
- 1 \leq x \leq 10^9
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出,其中 \mathrm{query}_i 表示 i第一个查询:
N Q
W_1 W_2 \dots W_N
C_1 C_2 \dots C_N
a_1 b_1
a_2 b_2
\vdots
a_{N-1} b_{N-1}
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q
每个查询均以以下格式之一给出:
1 v
2 v x
3 v
输出
让 m 是类型的数量-3 给出的查询。输出 m 行。的 i- 第行应包含以下问题的答案 i-第类型-3 查询。
示例输入 1
5 9 1 10 100 1000 10000 0 0 0 0 0 1 2 2 3 3 4 2 5 3 1 1 2 3 1 3 2 3 3 1 3 1 2 2 1 1 3 5
示例输出 1
11111 1 10 1100 10012
例如,对于第一个查询,从顶点可到达的顶点集 1 仅穿过颜色顶点 0 is \lbrace 1,2,3,4,5 \rbrace.
示例输入 2
10 25 1 10 100 1000 10000 100000 1000000 10000000 100000000 1000000000 0 1 0 0 0 1 0 0 0 0 1 2 1 3 2 4 4 5 4 6 2 7 5 8 8 9 6 10 3 4 1 8 2 6 100000 3 3 1 3 1 7 1 7 1 7 3 8 2 1 1 2 6 100000 2 8 10000000 1 5 2 5 10000 1 9 2 7 1000000 1 7 2 10 1000000000 1 9 1 6 1 9 1 1 3 7 2 5 10000 3 6
示例输出 2
110011000 101 10000000 2000000 2000301000