시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 285 84 44 39.640%

문제

제 3회 IUPC의 Calculate! 에서 교정이는 인규가 질문한 모든 논리연산에 대한 정답을 말하였다. 그 후 1년 뒤 제 4회 IUPC가 열리게 되었고, 인규는 이번에는 교정이를 꼭 골탕 먹이겠다는 생각을 갖고 교정이가 빠르게 대답을 못할만한 어려운 논리연산 문제를 준비했다. 

인규가 준비한 문제는 다음과 같다.

  • 정점이 N(≤ 100,000)개인 트리가 주어진다. 루트는 항상 1번 정점이다.  (트리란 N개의 정점과 N-1개의 간선으로 이루어 진 사이클이 존재하지 않는 하나의 컴포넌트를 가지는 연결 그래프이다)
  • 각 정점은 가중치 D(0 ≤ D ≤ 10,000)를 가진다.
  • M(≤ 500,000)개의 질의가 주어진다. 
  • 1 x 꼴로 주어지는 질의에는 정점 x를 포함한 x의 모든 자손들의 가중치를 전부 XOR한 값을 출력.
  • 2 x y 꼴로 주어지는 질의에는 정점 x를 포함한 x의 모든 자손들의 가중치에 각각 y(0 ≤ y ≤ 10,000)를 XOR을 함.

인규의 문제에 대한 교정이의 답변이 맞는지 확인하기 위하여 1 x 꼴로 주어지는 질의에 대한 답을 출력하는 프로그램을 작성해보자

입력

입력의 첫째 줄에 정점의 수 N(3 ≤ N ≤ 100,000)와 질의의 수 M(3 ≤ M ≤ 500,000)이 주어진다. 이 후 N-1줄에 A,B가 주어진다. 이는 A와 B가 연결되어 있다는 뜻이다. 다음 줄에 공백으로 분리 된 N개의 수가 주어진다. i번 째 수는 i번 째 정점의 가중치를 의미한다. 이후 M개의 줄에 질의가 주어진다.

출력

M개의 질의 중, 1 x 꼴로 주어지는 질의에 대한 답을 한줄 씩 출력한다.

예제 입력 1

5 4
1 2
2 3
2 4
3 5
1 2 3 4 5
1 1
2 3 100
2 1 94
1 4

예제 출력 1

1
90

예제 입력 2

7 10
1 2
1 3
1 4
4 5
4 6
6 7
49 38 29 40 3 59 0
2 7 45
2 3 30
1 7
1 5
1 1
2 1 2
1 4
2 6 15
1 1
1 2

예제 출력 2

45
3
41
61
43
36

출처

University > 인하대학교 > 2018 인하대학교 프로그래밍 경진대회(IUPC) C번

  • 시간 제한을 수정한 사람: isku
  • 문제를 만든 사람: jason9319