파일 업로드

놀이공원의 즐거움수치

profile
실행 시간 제한메모리 제한
2 초512 MB
📃 해결할 문제

놀이공원 관람객들은 자유롭게 돌아다니며 맛있는 음식을 먹고 다양한 놀이 시설을 즐깁니다 (롤러 코스터는 특히 인기가 많습니다).

NN개의 다른 놀이 시설이 있습니다 (2N1052 \leq N \leq 10^5). 어떤 쌍의 놀이 기구는 통로에 의해 연결되어 있으며, 총 N1N-1개의 통로가 있습니다. 이 통로들은 두 놀이 시설 사이의 경로를 구성하는 방식으로 연결되어 있으며, 각 놀이 시설 ii에는 정수 형태의 즐거움수치 eie_i가 존재합니다. 이 값은 하루 동안 변할 수 있습니다. 왜냐하면 어떤 놀이 시설은 아침에 더 매력적이고, 다른 놀이 시설은 오후에 더 매력적이기 때문입니다.

관람객이 놀이 시설 ii에서 놀이 시설 jj로 이동하게 되면, ii에서 jj로 가는 경로에 있는 모든 놀이 시설을 경험하게 됩니다. 

흥미롭게도 이 전체 경로의 총 즐거움 수치 값은 놀이 시설 iijj의 즐거움 수치 값을 포함해, 경로에 있는 모든 즐거움 수치 값의 비트단위 XOR으로 주어집니다.

다음 여행에서 관람객들이 사용할 예정인 경로의 즐거움 수치 값을 결정하는 데 도움을 주세요.

💻 입력

입력의 첫 번째 줄에는 NN와 질문의 수 QQ가 들어 있습니다 (1Q1051 \leq Q \leq 10^5). 

다음 줄에는 e1eNe_1 \ldots e_N이 포함되어 있습니다 (0ei1090 \leq e_i \leq 10^9). 그 다음 N1N-1개의 각 줄은 두 정수 놀이 시설 ID aabb로 경로를 설명합니다 (둘 다 범위는 1N1 \ldots N). 

마지막으로, 마지막 QQ개의 각 줄은 eie_i 값 중 하나를 업데이트하거나 경로의 즐거움 수치 값을 조회하는 질문을 설명합니다. "1 ii vv"의 형태의 줄은 eie_i를 값 vv로 업데이트해야 함을 나타내며, "2 ii jj"의 형태의 줄은 관광지 iijj를 연결하는 경로의 즐거움 수치 값을 조회하는 것입니다.

테스트 데이터의 최대 50% 포인트에서는 놀이 시설의 값이 변경되지 않습니다.

🖨️ 출력

"2 ii jj"의 형태의 각 질문에 대해, ii에서 jj로 가는 경로의 즐거움 수치 값을 한 줄에 출력합니다.


💻 예제 입력 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
🖨️ 예제 출력 1
21
20
4
20

출처: USACO 2019 February Contest, Gold Problem 1. Cow Land