시간 제한메모리 제한제출정답맞힌 사람정답 비율
2.5 초 1024 MB175252314.557%

문제

경곽마을은 $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$번 쿼리가 주어질 때마다 답을 한 줄에 하나씩 출력하라.

예제 입력 1

5
2 1
3 1
1 4
2 5
2 3
1 1 3
2 5
1 4 2
2 1
2 4

예제 출력 1

0
5
2

정기 모임이 개최될 때마다 각 집의 모임 참여 일수는 아래와 같이 변한다.