P6098 [USACO19FEB] Cow Land G

Cow Land is a special cow amusement park where cows can walk around, eat tasty grass, and visit different attractions (especially the roller coasters, which are very popular).

Cow Land has a total of $N$ different attractions ($2 \leq N \leq 10^5$). There are $N-1$ roads connecting pairs of attractions, which means there is exactly one simple path between any two attractions. Each attraction $i$ has an enjoyment value $e_i$, and this value may change. This is because some attractions are more appealing in the morning, while others are more appealing in the afternoon. Cows traveling from attraction $i$ to attraction $j$ can enjoy all the sights along the path from $i$ to $j$. The enjoyment value of this route is the bitwise XOR of the enjoyment values of all attractions on the path from $i$ to $j$ (including attraction $i$ and attraction $j$). Please help the cows determine the enjoyment value of the routes they plan to take during their trip to Cow Land.

The first line contains two integers $N, Q$ ($1 \leq Q \leq 10^5$). The next line contains $N$ integers, where the $i$-th integer $e_i$ represents the enjoyment value of attraction $i$. The next $N-1$ lines each contain two integers $a, b$, indicating that there is a road connecting attraction $a$ and attraction $b$. The last $Q$ lines each contain 3 integers, describing an operation as follows. 1. `1 i v`, meaning to change $e_i$ to $v$. 2. `2 i j`, meaning to ask what the enjoyment value of the route from attraction $i$ to attraction $j$ is.

For each operation of type 2, output the answer to the corresponding query.

Subtasks: For $50\%$ of the testdata, there are no update operations. Translated by ChatGPT 5