← 返回题目列表

AtCoder · abc460_g

G. 顶点翻转查询

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

分数: 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