시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
3 초 | 1024 MB | 2071 | 731 | 319 | 22.983% |
야구선수인 메시는 국제 메시 기구(IMO, International messi organization)의 금고 관리자이다. 트리를 사랑하는 메시는 금고를 금고 1이 루트인 트리 모양으로 연결해서 관리한다고 한다.
업무시간에 A+B를 풀고 있던 메시는 메일 하나를 받았는데, 그 메일에는 '메시 흑역사.jpg.exe'라는 이름의 첨부파일이 하나 있었다. 안 그래도 어제 도난 사건으로 금고 N개가 다 털려 0원밖에 남지 않아 해고당할 위기에 처했는데 흑역사까지 드러날 위기에 처한 메시는 한 치의 고민도 없이 첨부파일을 열었다. 그러자 이상한 콘솔 창이 등장했다!
금★고의 요☆정 지♨니! 금고 속의 돈을 늘려드립니다! 명령어를 입력하세요. 명령어의 목록은 다음과 같습니다.
메시는 도난 사건을 없던 일로 만들 기회라고 생각하여 명령어를 입력했지만, 이 파일은 당연하게도 바이러스라서 메시가 3개월간 짜던 A+B의 코드를 다 날려버렸다. 화가 난 메시는 위의 명령어를 실행하는 프로그램을 직접 만들기로 했다.
첫째 줄에 N, Q가 주어진다. (1 ≤ N ≤ 500,000, 1 ≤ Q ≤ 100,000)
다음 N-1줄 중 i번째 줄에는 Si, Ei가 주어지며, 이는 금고 Si와 금고 Ei가 연결되어 있다는 뜻이다. (1 ≤ Si, Ei ≤ N)
금고가 연결된 모양은 올바른 트리 모양이다.
다음 Q줄에는 명령어들이 한 줄에 하나씩 주어진다.
출력 명령어가 주어질 때마다 값을 출력한다. 단, 메시의 컴퓨터는 최신 트렌드인 4294967296비트 컴퓨터와는 다르게 32비트 컴퓨터이므로 232로 나눈 나머지를 대신 출력한다.
5 10 2 4 4 3 5 4 2 1 3 1 82 6 3 5 2 2 5 45 2 3 2 70 6 3 5 5 3 4 2 1 47 1 1 95 6 3 2 4 5 1 38
0 230 70 5875
명령어가 실행될 때마다 각 금고에 있는 돈은 다음과 같다.
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
---|---|---|---|---|---|---|---|---|---|---|---|
금고 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 95 | 95 | 3610 |
금고 2 | 0 | 0 | 0 | 45 | 115 | 115 | 115 | 5405 | 5500 | 5500 | 209000 |
금고 3 | 0 | 0 | 0 | 0 | 70 | 70 | 70 | 70 | 165 | 165 | 165 |
금고 4 | 0 | 0 | 0 | 45 | 115 | 115 | 115 | 115 | 210 | 210 | 7980 |
금고 5 | 0 | 0 | 0 | 45 | 45 | 45 | 45 | 45 | 140 | 140 | 5320 |
10 20 3 7 5 6 10 9 6 8 10 2 6 3 1 3 6 4 10 4 1 10 97 1 10 50 3 9 9 5 5 1 8 27 5 10 2 8 7 20 2 4 4 41 2 2 5 92 3 4 96 3 5 12 1 7 32 2 7 3 75 4 5 6 60 6 8 7 6 1 2 3 9 0 1 3 20 6 1 1 1 6 82
0 1617 6989 65471 0