問題一覧 > 通常問題

No.1641 Tree Xor Query

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 105
作問者 : harurunharurun / テスター : KazunKazun magstamagsta
2 ProblemId : 6667 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-08-06 20:40:03

問題文

$1\sim N$ の番号が付いた $N$ 頂点の木が与えられます。

この木の根は頂点 $1$ です。

各頂点にはコストがあり、頂点 $i$ のコストは $C_i$ です。 $(1≤i≤N)$

また、$i$ 番目の辺 $(1 \leq i \leq N-1)$ は 頂点 $a_i$ と頂点 $b_i$ を結びます。

以下のクエリが $Q$ 回与えられるので、処理してください。

  • $j$ 回目のクエリ $(1≤j≤Q)$ では以下の操作を行う。

    • $T_j=1$ のとき

    • $C_{x_j}$ を $C_{x_j} \oplus y_j$ で置き換える。

    • $T_j=2$ のとき

    • 頂点 $x_j$ を根とする部分木の全ての頂点のコストの xor を出力する。

ただし、 $a\oplus b$ はビット単位の xor を表します。

制約

  • $2 \leq N \leq 10^5$

  • $1 \leq Q \leq 10^5$

  • $0 \leq C_i<2^{10}$ $(1 \leq i \leq N)$

  • $1 \leq a_i,b_i \leq N$ $(1 \leq i \leq N-1)$

  • $T_j$ は $1$ または $2$ である。 $(1 \leq j \leq Q)$

  • $1 \leq x_j \leq N$ $(1 \leq j \leq Q)$

  • $T_j=1$ のとき、 $0 \leq y_j < 2^{10}$ $(1 \leq j \leq Q)$

  • $T_j=2$ のとき、 $y_j=0$ $(1≤j≤Q)$

  • クエリに $T_j=2$ $(1 \leq j \leq Q)$ は少なくとも $1$ つは含まれる。

  • 入力は全て整数である。

  • 与えられるグラフは木である。

入力

$N$ $Q$
$C_1$ $C_2$ $\dots$ $C_N$
$a_1$ $b_1$
$a_2$ $b_2$
$\vdots$
$a_{N-1}$ $b_{N-1}$
$T_1$ $x_1$ $y_1$
$T_2$ $x_2$ $y_2$
$\vdots$
$T_Q$ $x_Q$ $y_Q$
  • $1$ 行目には、 $N$ と $Q$ が空白区切りで与えられる。

  • $2$ 行目には、各頂点のコスト $C_1, C_2, \dots, C_N$ が空白区切りで与えられる。

  • $3$ 行目から $N+1$ 行目には、 $a_i$ と $b_i$ が空白区切りで与えられる。 $(1 \leq i \leq N-1)$

  • $N+2$ 行目から $N+Q+1$ 行目には、 $T_j,~x_j,~y_j$ が空白区切りで与えられる。 $(1 \leq j \leq Q)$

出力

$T_j=2~(1 \leq j \leq Q)$ であるような各クエリについて $1$ 行ずつ出力してください。

最後に改行してください。

サンプル

サンプル1
入力
3 3
1 2 3
1 2
1 3
1 2 3
1 3 4
2 1 0
出力
7

$1$ 回目のクエリで、 $C_2$ を $C_2\oplus y_1 = 2\oplus 3 = 1$ で置き換えます。

$2$ 回目のクエリで、 $C_3$ を $C_3\oplus y_2 = 3\oplus 4 = 7$ で置き換えます。

$3$ 回目のクエリで、 頂点 $1$ を根とする部分木のコストの総 xor $C_1\oplus C_2 \oplus C_3=1\oplus 1\oplus 7 =7 $ となるので、 $7$ を出力します。

サンプル2
入力
6 3
1 2 3 4 5 6
1 2
1 3
2 4
2 6
4 5
1 6 6
1 4 4
2 2 0
出力
7

サンプル3
入力
2 1
1 2
1 2
2 2 0
出力
2

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。