Binary Tree Queries

You are given a tree $T$ with $N$ vertices numbered from $1$ to $N$. Every vertex is colored either black or white.

$T$ is a binary tree. Initially, the root of $T$ is vertex $1$.

Process the following queries.

• 1 $i$: Change the root of $T$ to vertex $i$.
• 2 $i$: Toggle the color of vertex $i$. White becomes black, and black becomes white.
• 3 $i$: Let $a$ be the number of white vertices in the subtree rooted at vertex $i$ with respect to the current root. Let $b$ be the number of white vertices on the path from vertex $i$ to the current root. Both endpoints belong to the path. Print $|a-b|$.

It is guaranteed that $T$ is a binary tree regardless of which vertex is chosen as the root.

The input is given from Standard Input in the following format:

$T$ case$_1$ case$_2$ $\vdots$ case$_T$

Each case is given in the following format:

$N\ Q$ $C_1\ C_2\ \cdots\ C_N$ $u_1\ v_1$ $u_2\ v_2$ $\vdots$ $u_{N-1}\ v_{N-1}$ $q_1$ $q_2$ $\vdots$ $q_Q$

If $C_i=0$, vertex $i$ is black. If $C_i=1$, vertex $i$ is white.

The $j$-th edge connects vertices $u_j$ and $v_j$.

Each $q_j$ has one of the forms 1 $i$, 2 $i$, and 3 $i$.

For every type 3 query, print the answer on its own line.

• $1 \le T \le 100$.
• $1 \le N \le 100\,000$.
• $1 \le Q \le 100\,000$.
• $C_i \in \{0,1\}$ ($1 \le i \le N$).
• $1 \le u_j < v_j \le N$ ($1 \le j < N$).
• The given edges form a tree.
• The given tree is binary regardless of which vertex is chosen as the root.
• Every query satisfies $1 \le i \le N$.
• Every case contains at least one type 3 query.
• The sum of $N$ over all cases does not exceed $200\,000$.
• The sum of $Q$ over all cases does not exceed $200\,000$.