USACO

USACO 2019 February Contest, Gold

Problem 1. Cow Land

Contest has ended.

Log in to allow submissions in analysis mode

Cow Land is a special amusement park for cows, where they roam around, eat delicious grass, and visit different cow attractions (the roller cowster is particularly popular).

There are a total of $N$ different attractions ( $2 \leq N \leq 10^5$ ). Certain pairs of attractions are connected by pathways, $N-1$ in total, in such a way that there is a unique route consisting of various pathways between any two attractions. Each attraction $i$ has an integer enjoyment value $e_i$ , which can change over the course of a day, since some attractions are more appealing in the morning and others later in the afternoon.

A cow that travels from attraction $i$ to attraction $j$ gets to experience all the attractions on the route from $i$ to $j$ . Curiously, the total enjoyment value of this entire route is given by the bitwise XOR of all the enjoyment values along the route, including those of attractions $i$ and $j$ .

Please help the cows determine the enjoyment values of the routes they plan to use during their next trip to Cow Land.

INPUT FORMAT (file cowland.in):

The first line of input contains

$N$ and a number of queries

$Q$ (

$1 \leq Q \leq 10^5$ ). The next line contains

$e_1 \ldots e_N$ (

$0 \leq e_i \leq 10^9$ ). The next

$N-1$ lines each describe a pathway in terms of two integer attraction IDs

$a$ and

$b$ (both in the range

$1 \ldots N$ ). Finally, the last

$Q$ lines each describe either an update to one of the

$e_i$ values or a query for the enjoyment of a route. A line of the form "1

$i$

$v$ " indicates that

$e_i$ should be updated to value

$v$ , and a line of the form "2

$i$

$j$ " is a query for the enjoyment of the route connecting attractions

$i$ and

$j$ .

In test data worth at most 50% of points, there will be no changes to the values of the attractions.

OUTPUT FORMAT (file cowland.out):

For each query of the form "2

$i$

$j$ ", print on a single line the enjoyment of the route from

$i$ to

$j$ .

SAMPLE INPUT:

SAMPLE OUTPUT:

Problem credits: Charles Bailey

Contest has ended. No further submissions allowed.