Vertex Flip Query

• 时间限制：2 秒
• 内存限制：512 MiB

题目描述

有一棵包含 $N$ 个顶点的树，顶点编号为 $1$ 到 $N$。第 $i$ 条边连接顶点 $a_i$ 和 $b_i$。每个顶点 $i$ 都有权值 $W_i$ 和颜色 $C_i\in\lbrace 0,1\rbrace$。

你需要依次处理 $Q$ 次操作。操作分为以下三种：

• 1 v：将顶点 $v$ 的颜色 $C_v$ 变为 $1-C_v$。
• 2 v x：将顶点 $v$ 的权值 $W_v$ 变为 $W_v+x$。
• 3 v：设 $c$ 为顶点 $v$ 的颜色。输出从顶点 $v$ 出发，仅经过颜色为 $c$ 的顶点所能到达的所有顶点（包括顶点 $v$ 本身）的权值之和。

输入格式

输入以如下格式给出，其中 $\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$

输出格式

设第 $3$ 类操作的次数为 $m$。输出 $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

样例输入 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

数据范围

• $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<b_i\leq N$
• 保证输入的图是一棵树。
• $1\leq v\leq N$
• $1\leq x\leq 10^9$
• 所有输入值均为整数。