G - Vertex Flip Query 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 650 点

問題文

頂点に 1 から N の番号がついた N 頂点の木があります。i 本目の辺は頂点 a_i と頂点 b_i を結ぶ辺です。頂点 i には重み W_i と色 C_i \in \lbrace 0,1 \rbrace が設定されています。
クエリを Q 個処理してください。クエリは以下の 3 種類のいずれかです。

  • 1 v：頂点 v について C_v を 1-C_v に変更する。
  • 2 v x：頂点 v について W_v を W_v + x に変更する。
  • 3 v ：頂点 v の色を c とする。頂点 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

出力

与えられた 3 種類目のクエリの個数を m として、m 行出力せよ。i 行目には i 番目に与えられた 3 種類目のクエリの答えを 1 行で出力せよ。

入力例 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 番目のクエリでは、頂点 1 から色が 0 である頂点のみを通って到達可能な頂点の集合は \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

Score : 650 points

Problem Statement

There is a tree with N vertices numbered 1 to N. The i-th edge connects vertices a_i and b_i. Each vertex i has a weight W_i and a color C_i \in \lbrace 0,1 \rbrace.
Process Q queries. There are three types of queries as follows.

  • 1 v: Change C_v to 1 - C_v for vertex v.
  • 2 v x: Change W_v to W_v + x for vertex v.
  • 3 v: Let c be the color of vertex v. Output the sum of weights of all vertices reachable from vertex v by traveling only through vertices of color c (including vertex v itself).

Constraints

  • 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
  • The input graph is a tree.
  • 1 \leq v \leq N
  • 1 \leq x \leq 10^9
  • All input values are integers.

Input

The input is given from Standard Input in the following format, where \mathrm{query}_i denotes the i-th query:

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

Each query is given in one of the following formats:

1 v

2 v x

3 v

Output

Let m be the number of type-3 queries given. Output m lines. The i-th line should contain the answer for the i-th type-3 query.

Sample Input 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

Sample Output 1

11111
1
10
1100
10012

For example, for the first query, the set of vertices reachable from vertex 1 by traveling only through vertices of color 0 is \lbrace 1,2,3,4,5 \rbrace.

Sample Input 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

Sample Output 2

110011000
101
10000000
2000000
2000301000