M - 整数と根付き木 Editorial /

Time Limit: 8 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

N 頂点からなる根付き木 T があり、頂点には 1 から N の番号がついています。はじめは頂点 1 が根です。

また、N-1 本の辺のうち、i 番目の辺は頂点 a_i と頂点 b_i を結んでいます。

各頂点 v はそれぞれ整数の配列 A_v を持っています。はじめはすべて空です。

この根付き木 T に Q 回のクエリ操作を行います。クエリ操作は 3 種類あり、それぞれ以下の通りです。

  • 1 v x k ― 頂点 v の部分木に含まれる任意の頂点（頂点 v を含む） u に対して、 A_u に値 x を k 個追加する。
  • 2 v y z ― 頂点 v の配列 A_v に含まれる要素の中で、val xor y \leq z を満たす値 val の個数を求める。ここで、s xor t は s と t のビットごとの排他的論理和を指す。
  • 3 v ― 根を頂点 v に変更する。

あなたは、このようなクエリを順番に処理するプログラムを書かなくてはなりません。

制約

  • 入力は全て整数である。
  • 1 \leq N \leq 1.4 \times 10^5
  • 1 \leq Q \leq 1.4 \times 10^5
  • 1 \leq a_i, b_i \leq N (1 \leq i \leq N-1)
  • 1 \leq v \leq N
  • 0 \leq x, y, z < 2^{30}
  • 1 \leq k \leq 10^9
  • 与えられるグラフは木である。

入力

入力は以下の形式で標準入力から与えられる。

N
a_1 b_1
a_2 b_2
:
a_{N-1} b_{N-1}
Q
Query_1
Query_2
:
Query_Q
  • Query_i は 1 v x k、2 v y z もしくは 3 v の形式で一行ごとに与えられる。

出力

2 v y z の形式のクエリに対し、与えられた順番に答えを出力せよ。

入力例 1

4
1 2
1 3
3 4
14
1 1 1 1
1 2 2 1
1 3 3 1
2 1 0 4
2 2 1 3
2 4 3 2
3 4
1 3 3 1
1 4 4 1
1 1 1 1
1 2 2 1
2 1 0 4
2 2 1 3
2 4 3 2

出力例 1

1
2
2
4
5
2
  • 1 個目のクエリでは、A_1 と A_2 と A_3 と A_4 に値 1 を 1 つずつ追加します。
  • 2 個目のクエリでは、A_2 に値 2 を 1 つ追加します。
  • 3 個目のクエリでは、A_3 と A_4 に値 3 を 1 つずつ追加します。
  • 4 個目のクエリでは、根を頂点 1 から頂点 4 に変更します。
  • 5 個目のクエリでは、A_1 = \{1\} であり 1 xor 0 = 1 なので 4 以下の値の個数である 1 を出力します。
  • 6 個目のクエリでは、A_2 = \{1,2\} であり 1 xor 1 = 0 、2 xor 1 = 3 なので 3 以下の値の個数である 2 を出力します。
  • 7 個目のクエリでは、A_4 = \{1,3\} であり 1 xor 3 = 2 、3 xor 3 = 0 なので 2 以下の値の個数である 2 を出力します。
  • 8 個目のクエリでは、A_1 と A_2 と A_3 に値 3 を 1 つずつ追加します。
  • 9 個目のクエリでは、A_1 と A_2 と A_3 と A_4 に値 4 を 1 つずつ追加します。
  • 10 個目のクエリでは、A_1 と A_2 に値 1 を 1 つずつ追加します。
  • 11 個目のクエリでは、A_2 に値 2 を 1 つ追加します。
  • 12 個目のクエリでは、A_1 = \{1,3,4,1\} であり 1 xor 0 = 1 、3 xor 0 = 3 、4 xor 0 = 4 、1 xor 0 = 1 なので 4 以下の値の個数である 4 を出力します。
  • 13 個目のクエリでは、A_2 = \{1,2,3,4,1,2\} であり 1 xor 1 = 0 、2 xor 1 = 3 、3 xor 1 = 2 、4 xor 1 = 5 、1 xor 1 = 0 、2 xor 1 = 3 なので 3 以下の値の個数である 5 を出力します。
  • 14 個目のクエリでは、A_4 = \{1,3,4\} であり 1 xor 3 = 2 、3 xor 3 = 0 、4 xor 3 = 7 なので 2 以下の値の個数である 2 を出力します。

入力例 2

1
11
1 1 4 1
1 1 14 2
1 1 10 4
1 1 8 8
1 1 12 16
1 1 2 32
1 1 6 64
1 1 0 128
2 1 0 10
2 1 10 10
2 1 8 10

出力例 2

237
190
190

入力例 3

1
11
1 1 0 1000000000
1 1 0 1000000000
1 1 0 1000000000
1 1 0 1000000000
1 1 0 1000000000
1 1 0 1000000000
1 1 0 1000000000
1 1 0 1000000000
1 1 0 1000000000
1 1 0 1000000000
2 1 0 2

出力例 3

10000000000

出力は 32 ビット整数型に収まるとは限りません。

入力例 4

1
2
1 1 1 123
2 1 0 1073741823

出力例 4

123