트리와 쿼리 18

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

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

• 1 u v: 트리의 루트를 정점 u라 하였을 때, 정점 v를 루트로 하는 서브트리의 모든 정점 i의 Ai에 1을 더한다.
• 2 u v: 정점 u에서 정점 v로 가는 유일한 경로에 있는 모든 정점 i의 Ai에 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개 줄에 트리의 간선이 주어진다. 각 줄에는 공백으로 구분된 두 수 u와 v가 주어지고, u와 v를 연결하는 간선이 있다는 것을 의미한다. (1 ≤ u, v ≤ N)

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

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

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

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

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