No.1641 Tree Xor Query
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$
When $T_j=2$
Replace $C_{x_j}$ with $C_{x_j} \oplus y_j$.
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もしくは右上の雲マークをクリックしてアカウントを作成してください。
harurun
Kazun
magsta