Tree and Queries 18

There is a tree with $N$ vertices. The vertices are numbered from 1 to $N$, and vertex $i$ stores an integer $A_i$. Initially, every $A_i$ is 0. ($1 \le i \le N$)

You must perform a total of $Q$ queries of the following forms.

• 1 u v: Root the tree at vertex $u$. Add 1 to $A_i$ for every vertex $i$ in the subtree rooted at vertex $v$.
• 2 u v: Add 1 to $A_i$ for every vertex $i$ on the unique path from vertex $u$ to vertex $v$.
• 3 v: Print $\sum_{i=1}^{N} A_i \times dist(v, i)$. $dist(x, y)$ is the number of edges on the path from vertex $x$ to vertex $y$.

The first line contains $N$. ($1 \le N \le 200{,}000$)

Each of the next $N-1$ lines contains two integers $u$ and $v$, separated by a space, meaning there is an edge between $u$ and $v$. ($1 \le u, v \le N$)

The next line contains $Q$, the number of queries. ($1 \le Q \le 200{,}000$)

Each of the next $Q$ lines contains one query in one of the formats above. ($1 \le u, v \le N$)

At least one query of type 3 is given.

For each query of type 3, print the result on its own line, in the order the queries are given.