#PU921. USACO 2019 February Contest, Gold — Problem 1. Cow Land
USACO 2019 February Contest, Gold — Problem 1. Cow Land
USACO 2019 February Contest, Gold — Problem 1. Cow Land
题目描述
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 different attractions (). Certain pairs of attractions are connected by pathways, in total, in such a way that there is a unique route consisting of various pathways between any two attractions. Each attraction has an integer enjoyment value , 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 to attraction gets to experience all the attractions on the route from to . 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 and . Please help the cows determine the enjoyment values of the routes they plan to use during their next trip to Cow Land.
输入格式
The first line of input contains and a number of queries (). The next line contains (). The next lines each describe a pathway in terms of two integer attraction IDs and (both in the range ). Finally, the last lines each describe either an update to one of the values or a query for the enjoyment of a route. A line of the form "1 " indicates that should be updated to value , and a line of the form "2 " is a query for the enjoyment of the route connecting attractions and . In test data worth at most 50% of points, there will be no changes to the values of the attractions.
输出格式
For each query of the form "2 ", print on a single line the enjoyment of the route from to .
数据范围
(见题面原文)
样例
样例 1
5 5
1 2 4 8 16
1 2
1 3
3 4
3 5
2 1 5
1 1 16
2 3 5
2 1 5
2 1 3
21
20
4
20
Problem credits: Charles Bailey