RiseOJ – 카우 랜드

설명

카우 랜드는 소들을 위한 특별한 놀이공원으로, 소들은 이곳을 돌아다니며 맛있는 풀을 뜯고 다양한 소 놀이기구를 즐긴다(롤러 카우스터가 특히 인기가 많다).

놀이기구는 총 $$N$$ 개 있다 ( $2 \leq N \leq 10^5$ ). 특정 놀이기구 쌍들은 총 $$N-1$$ 개의 산책로로 연결되어 있으며, 임의의 두 놀이기구 사이에는 여러 산책로로 이루어진 유일한 경로가 존재한다. 각 놀이기구 $$i$$ 에는 정수 즐거움 값 $$e_i$$ 가 있는데, 어떤 놀이기구는 아침에, 어떤 놀이기구는 오후 늦게 더 매력적이므로 이 값은 하루 동안 변할 수 있다.

놀이기구 $$i$$ 에서 놀이기구 $$j$$ 로 이동하는 소는 $$i$$ 에서 $$j$$ 까지의 경로 위에 있는 모든 놀이기구를 경험하게 된다. 흥미롭게도, 이 전체 경로의 총 즐거움 값은 놀이기구 $$i$$ 와 $$j$$ 의 것을 포함하여 경로 위의 모든 즐거움 값의 비트 단위 XOR로 주어진다.

소들이 다음 카우 랜드 방문에서 이용할 경로들의 즐거움 값을 구하는 것을 도와주자.

문제 제공: Charles Bailey

제약

문제 제공: Charles Bailey

입력 형식

첫째 줄에 $$N$$ 과 질의의 수 $$Q$$ ( $1 \leq Q \leq 10^5$ )가 주어진다. 다음 줄에 $e_1 \ldots e_N$ ( $0 \leq e_i \leq 10^9$ )이 주어진다. 다음 $$N-1$$ 개의 줄 각각은 두 정수 놀이기구 번호 $$a$$ 와 $$b$$ (둘 다 $1 \ldots N$ 범위)로 산책로 하나를 나타낸다. 마지막으로, 마지막 $$Q$$ 개의 줄 각각은 $$e_i$$ 값 중 하나에 대한 갱신 또는 경로의 즐거움에 대한 질의를 나타낸다. "1 $$i$$ $$v$$ " 형태의 줄은 $$e_i$$ 를 값 $$v$$ 로 갱신해야 함을 나타내고, "2 $$i$$ $$j$$ " 형태의 줄은 놀이기구 $$i$$ 와 $$j$$ 를 연결하는 경로의 즐거움에 대한 질의이다.

최대 50%의 점수에 해당하는 테스트 데이터에서는 놀이기구 값의 변경이 없다.

출력 형식

"2 $$i$$ $$j$$ " 형태의 각 질의에 대해, $$i$$ 에서 $$j$$ 까지의 경로의 즐거움을 한 줄에 하나씩 출력한다.

Standard input / output

This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:

입력을 읽을 파일 cowland.in · 출력을 쓸 파일 cowland.out

예제 1

입력

출력

문제 정보

riseoj 작성

출처 올림피아드 > USACO > 2018-2019 > February > Gold

올림피아드 > USACO > 2018-2019 > February > Gold

태그

JudgeUSACO

카우 랜드

평가 및 의견

풀이 제출