시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 820 | 337 | 247 | 50.823% |
제 3회 IUPC의 Calculate! 에서 교정이는 인규가 질문한 모든 논리연산에 대한 정답을 말하였다. 그 후 1년 뒤 제 4회 IUPC가 열리게 되었고, 인규는 이번에는 교정이를 꼭 골탕 먹이겠다는 생각을 갖고 교정이가 빠르게 대답을 못할만한 어려운 논리연산 문제를 준비했다.
인규가 준비한 문제는 다음과 같다.
인규의 문제에 대한 교정이의 답변이 맞는지 확인하기 위하여 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 꼴로 주어지는 질의에 대한 답을 한줄 씩 출력한다.
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 90
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
45 3 41 61 43 36