35059번 - 정기 모임 7

문제

경곽마을은 $N$개의 집과 $N - 1$개의 도로로 구성되어 있는 트리 구조이다. 경곽마을의 이장 경곽이는 도로가 양방향으로 연결되어 있다는 사실에 불만을 가지고 모든 도로를 단방향으로 바꾸어 버렸다. 이런 상황에서 경곽이는 경곽마을에서 총 $M$개의 정기 모임을 개최하고자 한다.

정기 모임을 $v$번 집에서 $x$일 동안 한다면 $v$번 집을 포함하여, $v$번 집으로 이동할 수 있는 모든 집에서 $v$번 집으로 이동해 $x$일 동안 모임에 참석한다. 각 집이 정기 모임에 참석하기 위해 이동하는 데 걸리는 시간은 없으며, 정기 모임들은 서로 겹치지 않게 개최된다.

그러던 중 이장 경곽이는 각 집이 총 며칠 동안 정기 모임에 참석했는지가 궁금해졌다. 경곽이의 질문을 해결해 주자.

입력

첫 번째 줄에 트리의 정점의 개수 $N$이 주어진다. (2ドル \leq N \leq 200 ,円 000$)

두 번째 줄부터 $N - 1$개의 줄에 걸쳐 정수 $u,ドル $v$가 공백으로 구분되어 주어진다. 이는 $u$번 집과 $v$번 집 사이에 $u \to v$ 방향으로 잇는 도로가 있음을 의미한다. (1ドル \leq u, ,円 v \leq N$)

$N + 1$ 번째 줄에 경곽마을에서 개최된 정기 모임의 개수 $M$과 경곽이의 질문의 개수 $Q$가 공백으로 구분되어 주어진다. (1ドル \leq M, ,円 Q \leq 100 ,円 000$)

$N + 2$ 번째 줄부터 $M + Q$개의 줄에 걸쳐, 아래와 같은 형식으로 입력이 주어진다.

• 1ドル$ $v$ $x$: $v$번 집에서 $x$일 동안 정기 모임이 개최된다. (1ドル \leq v \leq N$; 1ドル \leq x \leq 10^9$)
• 2ドル$ $u$: 현재까지 $u$번 집이 며칠 동안 정기 모임에 참석했는지를 출력한다. (1ドル \leq u \leq N$)

1ドル$번 쿼리는 총 $M$개, 2ドル$번 쿼리는 총 $Q$개 주어진다.

출력

2ドル$번 쿼리가 주어질 때마다 답을 한 줄에 하나씩 출력하라.

제한

노트