Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 131072/131072 K (Java/Others)

Dylans is given a tree with $N$ nodes.

All nodes have a value $A[i]$.Nodes on tree is numbered by $1 \sim N$.

Then he is given $Q$ questions like that:

①$0 \ x \ y$：change node $x's$ value to $y$

②$1 \ x \ y$：For all the value in the path from $x$ to $y$,do they all appear even times?

For each ② question,it guarantees that there is at most one value that appears odd times on the path.

$1 \leq N,Q \leq 100000$, the value $A[i]∈N$ and $A[i] \leq 100000$

All nodes have a value $A[i]$.Nodes on tree is numbered by $1 \sim N$.

Then he is given $Q$ questions like that:

①$0 \ x \ y$：change node $x's$ value to $y$

②$1 \ x \ y$：For all the value in the path from $x$ to $y$,do they all appear even times?

For each ② question,it guarantees that there is at most one value that appears odd times on the path.

$1 \leq N,Q \leq 100000$, the value $A[i]∈N$ and $A[i] \leq 100000$

In the first line there is a test number $T$.

($T \leq 3$ and there is at most one testcase that $N > 1000$)

For each testcase:

In the first line there are two numbers $N$ and $Q$.

Then in the next $N - 1$ lines there are pairs of $(X,Y)$ that stand for a road from $x$ to $y$.

Then in the next line there are $N$ numbers $A_1..A_N$ stand for value.

In the next $Q$ lines there are three numbers$(opt,x,y)$.

($T \leq 3$ and there is at most one testcase that $N > 1000$)

For each testcase:

In the first line there are two numbers $N$ and $Q$.

Then in the next $N - 1$ lines there are pairs of $(X,Y)$ that stand for a road from $x$ to $y$.

Then in the next line there are $N$ numbers $A_1..A_N$ stand for value.

In the next $Q$ lines there are three numbers$(opt,x,y)$.

For each question ② in each testcase,if the value all appear even times output "-1",otherwise output the value that appears odd times.

提交代码