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
以上就是關于【USACO 2019 February Contest Gold Problem 1 Cow Land】的解答，如需了解學校/賽事/課程動態，可至翰林教育官網獲取更多信息。
往期文章閱讀推薦：
耗時一年備考 USACO 卻毫無收獲？一文教你找準最佳備考起步時間！
2026 NOAI國際AI奧賽中國站即將開考！賽事地址&日程已出！
翰林AMC8視頻課重磅上線！
國際競賽真題資源免費領取
