P3248 [HNOI2016] Tree

Little A wants to build a very large tree, but his materials are limited, so he uses a small trick. Initially, Little A has a tree with $N$ nodes, numbered $1, 2, ..., N$, where node $1$ is the root; we call this the "template tree". Little A decides to construct a large tree based on this template tree. The construction proceeds as follows: 1. Copy the template tree as the initial large tree. 2. Repeat steps (2.1)–(2.3) $M$ times. (2.1) Choose two integers $a, b$, where $1 \leq a \leq N$, $1 \leq b \leq$ the current number of nodes in the large tree. (2.2) Copy the subtree of the template tree rooted at node $a$, and attach it under node $b$ in the large tree (that is, after copying, the subtree rooted at node $a$ from the template tree becomes a subtree of node $b$ in the large tree). (2.3) Renumber the newly added nodes in the large tree according to their order in the template tree. For example, suppose the large tree has $L$ nodes before step (2.2), and the subtree rooted at $a$ in the template tree has $C$ nodes. Then the $C$ newly added nodes will be numbered $L+1, L+2, ..., L+C$ in the large tree; the relative order of these $C$ node numbers in the large tree is consistent with the order of the corresponding $C$ nodes in the template tree. An example is given below. Suppose the template tree is as follows:  According to step (1), the initial large tree is the same as the template tree. In step (2.1), suppose we choose $a=4, b=3$. After performing steps (2.2) and (2.3), the new large tree is as shown below:  Now he asks you for the distances between some pairs of nodes in the tree.

The first line contains three integers $N, M, Q$, separated by spaces, where $N$ is the number of nodes in the template tree, $M$ is the number of repetitions of the operation in step (2), and $Q$ is the number of queries. The next $N-1$ lines each contain two integers $fr, to$, representing an edge in the template tree. Then there are $M$ lines, each containing two integers $x, to$, representing one operation that copies the subtree rooted at $x$ in the template tree and attaches it as a subtree of node $to$ in the large tree. Then there are $Q$ lines, each containing two integers $fr, to$, asking for the distance between nodes $fr$ and $to$ in the large tree. $N, M, Q \leq 100000$.

Output $Q$ lines, each containing one integer. The $i$-th line is the answer to the $i$-th query.

After two operations, the large tree becomes the shape shown below:  There are $6$ edges between nodes $6$ and $9$, so the distance is $6$. Similarly, there are $3$ edges between nodes $1$ and $8$. There are also $3$ edges between nodes $5$ and $3$. Translated by ChatGPT 5