시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 512 MB 13 5 3 30.000%

문제

N개의 정점으로 이루어진 트리가 있다. 정점은 1번부터 N번까지 번호가 매겨져 있고, i번 정점에는 정수 Ai가 저장되어 있다. 처음 상태에서 Ai=0이다. (1 ≤ iN

당신은 다음과 같은 쿼리를 총 Q번 수행해야 한다.

  • 1 u v: 트리의 루트를 정점 u라 하였을 때, 정점 v를 루트로 하는 서브트리의 모든 정점 iAi에 1을 더한다.
  • 2 u v: 정점 u에서 정점 v로 가는 유일한 경로에 있는 모든 정점 iAi에 1을 더한다.
  • 3 v: $\sum_{i = 1}^{N} A_i \times dist(v, i)$를 출력한다. $dist(x, y)$는 정점 x에서 정점 y로 가는 경로에 있는 간선의 수를 의미한다.

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000)

다음 N-1개 줄에 트리의 간선이 주어진다. 각 줄에는 공백으로 구분된 두 수 uv가 주어지고, uv를 연결하는 간선이 있다는 것을 의미한다. (1 ≤ u, vN)

다음 줄에는 쿼리의 개수 Q가 주어진다. (1 ≤ Q ≤ 200,000)  

다음 Q개의 줄에는 한 줄에 하나씩 다음과 같은 형식 중 하나로 쿼리가 주어진다.

  • 1 u v (1 ≤ u, vN)
  • 2 u v (1 ≤ u, vN)
  • 3 v (1 ≤ vN)

3번 쿼리는 한 번 이상 주어진다.

출력

각각의 3번 쿼리의 결과를 순서대로 한 줄에 하나씩 출력한다.

예제 입력 1

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

예제 출력 1

1
5

출처