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 NN different attractions (2≤N≤1052≤N≤105). Certain pairs of attractions are connected by pathways, N−1N−1 in total, in such a way that there is a unique route consisting of various pathways between any two attractions. Each attraction ii has an integer enjoyment value eiei, 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 ii to attraction jj gets to experience all the attractions on the route from ii to jj. 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 ii and jj.
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 NN and a number of queries QQ (1≤Q≤1051≤Q≤105). The next line contains e1…eNe1…eN (0≤ei≤1090≤ei≤109). The next N−1N−1 lines each describe a pathway in terms of two integer attraction IDs aa and bb (both in the range 1…N1…N). Finally, the last QQ lines each describe either an update to one of the eiei values or a query for the enjoyment of a route. A line of the form "1 ii vv" indicates that eiei should be updated to value vv, and a line of the form "2 ii jj" is a query for the enjoyment of the route connecting attractions ii and jj.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 ii jj", print on a single line the enjoyment of the route from ii to jj.
SAMPLE INPUT:
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
SAMPLE OUTPUT:
21 20 4 20
Problem credits: Charles Bailey
国际竞赛真题资料-点击免费领取！
美高学分项目重磅来袭！立即了解
AMC8备考管家服务全新上线！
