트리와 쿼리 18

정점이 $N$개인 트리가 있다. 정점은 1번부터 $N$번까지 번호가 매겨져 있고, $i$번 정점에는 정수 $A_i$가 저장되어 있다. 처음에는 모든 $A_i$가 0이다. ($1 \le i \le N$)

다음 형식의 쿼리를 총 $Q$번 수행해야 한다.

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

첫째 줄에 $N$이 주어진다. ($1 \le N \le 200{,}000$)

다음 $N-1$개 줄에 트리의 간선이 주어진다. 각 줄에는 공백으로 구분된 두 정수 $u$와 $v$가 주어지며, 두 정점을 잇는 간선이 있다는 뜻이다. ($1 \le u, v \le N$)

다음 줄에는 쿼리의 개수 $Q$가 주어진다. ($1 \le Q \le 200{,}000$)

다음 $Q$개 줄에는 위 형식 중 하나로 쿼리가 한 줄에 하나씩 주어진다. ($1 \le u, v \le N$)

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

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