問題一覧 > 通常問題

No.1641 Tree Xor Query

レベル : / AI推定難易度 : 1450 / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 147
作問者 : harurun / テスター : 👑 Kazun magsta
お気に入りにしたユーザー ProblemId : 6667 / 自分の提出
問題文最終更新日: 2021-08-06 20:40:03
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 308 (順位表) の他の問題:

Problem Statement

You are given a tree with $N$ vertices numbered $1\sim N$.

The root of this tree is vertex $1$.

Each vertex has a cost, and the cost of vertex $i$ is $C_i$. $(1≤i≤N)$

Also, the $i$-th edge $(1 \leq i \leq N-1)$ connects vertex $a_i$ and vertex $b_i$.

You are given the following queries $Q$ times; process them.

  • In the $j$-th query $(1≤j≤Q)$, perform the following operation.

    • When $T_j=1$

    • Replace $C_{x_j}$ with $C_{x_j} \oplus y_j$.

    • When $T_j=2$

    • Output the xor of the costs of all vertices in the subtree rooted at vertex $x_j$.

Here, $a\oplus b$ denotes the bitwise xor.

Constraints

  • $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$ is $1$ or $2$. $(1 \leq j \leq Q)$

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

  • When $T_j=1$, $0 \leq y_j < 2^{10}$ $(1 \leq j \leq Q)$

  • When $T_j=2$, $y_j=0$ $(1≤j≤Q)$

  • The queries include $T_j=2$ $(1 \leq j \leq Q)$ at least $1$ time.

  • All input values are integers.

  • The given graph is a tree.

Input

$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$
  • Line $1$ contains $N$ and $Q$, separated by a space.

  • Line $2$ contains the costs of the vertices $C_1, C_2, \dots, C_N$, separated by spaces.

  • Lines $3$ through $N+1$ contain $a_i$ and $b_i$, separated by a space. $(1 \leq i \leq N-1)$

  • Lines $N+2$ through $N+Q+1$ contain $T_j,~x_j,~y_j$, separated by spaces. $(1 \leq j \leq Q)$

Output

For each query with $T_j=2~(1 \leq j \leq Q)$, output $1$ line.

Print a newline at the end.

Sample

Sample 1
Input
3 3
1 2 3
1 2
1 3
1 2 3
1 3 4
2 1 0
Output
7

In query number $1$, replace $C_2$ with $C_2\oplus y_1 = 2\oplus 3 = 1$.

In query number $2$, replace $C_3$ with $C_3\oplus y_2 = 3\oplus 4 = 7$.

In query number $3$, the total xor of the costs in the subtree rooted at vertex $1$ is $C_1\oplus C_2 \oplus C_3=1\oplus 1\oplus 7 =7 $, so output $7$.

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

Sample 3
Input
2 1
1 2
1 2
2 2 0
Output
2

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