P4618 [SDOI2018] Original Problem Identification

- Input file: old.in - Output file: old.out - Time limit: 10 seconds. - Memory limit: 512 megabytes.

“Human problem database” Little $Q$ practices very hard and has solved over ten thousand problems. Whenever someone asks him about a problem, Little $Q$ can tell within $1$ second which $OJ$ and which problem it is. Therefore, Little $Q$ is like an “original problem search engine”. One day, Little $Q$ came to a rooted tree with $n$ nodes. The root is node $1$, and each node has a problem printed on it. With his huge amount of experience, Little $Q$ quickly identified the source of every problem, and found that some problems had been reposted many times. He classified the problem on each node: the problem type of node $i$ is $a_i$. The problems at node $i$ and node $j$ come from the same source if and only if $a_i = a_j$. Solving the same problem multiple times does not improve skill, except increasing the number of $AC$ submissions. To investigate the quality of the problems on this tree, Little $Q$ will ask the following two types of queries for a total of $m$ times: - $1$ $x$ $y$: If you solve all problems on the shortest path from node $x$ to node $y$ (including $x$ and $y$), how many essentially different problems can you solve in total? - $2$ $A$ $B$: If you choose a node $x$ uniformly at random on the shortest path from node $A$ to the root (including $A$ and the root), and choose a node $y$ uniformly at random on the shortest path from node $B$ to the root (including $B$ and the root), what is the expected answer to query $1$ $x$ $y$? Let $cnt_x$ denote the number of nodes on the shortest path from node $x$ to the root. Since Little $Q$ does not like fractions, and the answer to the second type of query can always be written as $\frac{ans}{{cnt_A}\times{cnt_B}}$, you only need to output the value of $ans$. Identifying these problems has consumed too much of Little $Q$’s energy, so he cannot compute the answers to these simple queries by himself. Please write a program to answer all $m$ queries for Little $Q$.

The first line contains a positive integer $T$, denoting the number of testdata. For each testdata, the first line contains $5$ positive integers $n, p, SA, SB, SC$, where $n$ is the number of nodes in the tree. To reduce the input size to some extent, the tree edges and the problem type array $a[]$ will be generated by the following code: ``` unsigned int SA, SB, SC; unsigned int rng61(){ SA ^= SA > 5; SA ^= SA

For each testdata, output $m$ lines, one integer per line, answering each query in order.

- $1 \le T \le 3,2 \le p \le n \le 10^5,1 \le m \le 2\times 10^5$. - $10^4 \le SA, SB, SC \le 10^6,1 \le x, y, A, B \le n$. Subtask $1$ ($30$ points): only contains type $1$ queries. Subtask $2$ ($30$ points): satisfies $p = n$. Subtask $3$ ($40$ points): no additional constraints. Translated by ChatGPT 5