408073: GYM102979 A Another Tree Queries Problem
Description
You have a tree of $$$N$$$ vertices. Vertices are enumerated by sequential integers from 1 to $$$N$$$, and the $$$i$$$-th vertex contains the variable $$$A_i$$$. Initially $$$A_i$$$ = 0 ($$$1 \le i \le N$$$).
You have to process $$$Q$$$ queries. Each query is one of the following:
- "1 $$$u$$$ $$$v$$$": Root the tree at vertex $$$u$$$, consider the subtree of vertex $$$v$$$, and for each vertex $$$i$$$ in the subtree of $$$v$$$, increase $$$A_i$$$ by one.
- "2 $$$u$$$ $$$v$$$": For each vertex $$$i$$$ in the unique simple path from $$$u$$$ to $$$v$$$, increase $$$A_i$$$ by one.
- "3 $$$v$$$": Print $$$\displaystyle \sum\limits_{i=1}^N \mathrm{dist} (v, i) \cdot A_i$$$, where $$$\mathrm{dist} (x, y)$$$ is the number of edges in the path from vertex $$$x$$$ to vertex $$$y$$$.
The first line contains an integer $$$N$$$, the number of vertices ($$$1 \le N \le 2 \cdot 10^5$$$).
The next $$$N - 1$$$ lines contain the description of the tree. Each such line contains two integers $$$u$$$ and $$$v$$$ separated by a space, meaning that there is an edge connecting $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le N$$$). It is guaranteed that the resulting graph is a tree.
The next line contains an integer $$$Q$$$, the number of queries ($$$1 \le Q \le 2 \cdot 10^5$$$).
The next $$$Q$$$ lines contain queries, one per line. Each query is given in one of the formats described above ($$$1 \le u, v \le N$$$). You may assume that there is at least one query of type "3".
OutputFor each query of type "3", print the result on a separate line.
ExampleInput5 4 2 2 5 1 5 1 3 5 2 2 4 3 4 2 1 5 2 5 5 3 2Output
1 5