성대나라의 물탱크
시간 제한1초메모리 제한256 MB
수도를 루트로 하는 물탱크 트리가 주어진다. 도시 A에 물을 추가하면 수도에서 A까지의 경로를 따라 1, 2, 3, ... L이 더해진다. 특정 도시에 현재 저장된 물의 양을 묻는 질의에 답한다.
문제
성대나라에는 각 도시마다 가뭄에 대비하는 물탱크가 하나씩 있다. 이 물탱크들은 모두 연결되어 있으며, 수도가 루트인 트리 형태를 이룬다. 성대나라는 물탱크의 물로 가뭄을 버텨냈지만, 그 영향으로 모든 물탱크가 비어버렸다.
성대나라의 물관리 시스템은 조금 특수해서, 물은 항상 다음 방식으로 채워진다.
A번 도시에 물을 채우기로 하면, 수도에서 A번 도시까지 잇는 경로를 따라 수도부터 차례대로 1L, 2L, …가 채워진다. 따라서 A번 도시에는 (수도부터 A번 도시까지의 도시 수) L가 추가된다.
예를 들어 아래 그림처럼 물탱크가 연결되어 있을 때 "4번 도시에 물을 채운다"라고 하면 1번 도시에 1L, 4번 도시에 2L의 물이 추가된다. "5번 도시에 물을 채운다"라고 하면 1번 도시에 1L, 2번 도시에 2L, 5번 도시에 3L의 물이 추가된다.
성대나라의 물탱크 관리 담당인 균관이는 어느 도시에 몇 리터의 물이 저장되어 있는지 궁금해질 때마다 알아내고 싶어 한다. 균관이를 도와주는 프로그램을 만들어보자.
입력
첫째 줄에 성대나라의 도시의 수 N (1 ≤ N ≤ 200,000)과 수도의 번호 C (1 ≤ C ≤ N)가 공백으로 구분되어 주어진다.
둘째 줄부터 N-1개의 줄에 연결되어 있는 두 도시의 번호 쌍 x, y가 공백으로 구분되어 주어진다 (1 ≤ x, y ≤ N, x ≠ y). 물탱크의 연결 형태는 트리 구조임이 보장된다. N+1번째 줄에 질의의 수 Q (1 ≤ Q ≤ 200,000)가 주어진다. N+2번째 줄부터 Q개의 줄에 질의가 들어온다. 질의는 다음 두 종류 중 하나로 주어진다.
- 1 A : A번 도시에 물을 채운다.
- 2 A : 현재 A번 도시에 얼마만큼의 물이 채워져 있는지 출력하라.
두 경우 모두 1 ≤ A ≤ N을 만족한다.
출력
2로 시작하는 질의가 올 때마다 그 결과를 한 줄에 하나씩 출력한다.