P5206 [WC2019] Counting Trees

The white rabbit likes trees. The white cloud likes counting. There are $n$ mice. The white rabbit uses $n - 1$ blue ropes to connect them into a tree; each blue rope connects two mice. The white cloud uses $n - 1$ red ropes to connect them into a tree; each red rope connects two mice. The white cloud wants to assign a number to each mouse. This number can be any integer in $[1, y]$. The white rabbit gives the white cloud a requirement: for two mice $p, q$, if there exists a path connecting these two mice that belongs to both trees, then $p$ and $q$ must be assigned the same integer. “Having a path that belongs to both trees” means: there exists a sequence $(a_1 = p, a_2, \cdots , a_m = q)$ such that for all $i \in [1, m - 1]$, $a_i$ and $a_{i+1}$ are directly connected by both a red rope and a blue rope. The white cloud wants to know: how many different assignment schemes are there? The mice keep struggling, trying to break free from the ropes. Before the white cloud can figure it out, the mice bite off all the red ropes. The white rabbit is somewhat annoyed, but still wants to know the answer. So he asks the white cloud: over all possible connection schemes of the red ropes, what is the total sum of the answers (that is, sum the number of assignment schemes over all red-rope connection schemes)? The mice keep struggling, trying to break free from the ropes. Before the white cloud can figure it out, the mice bite off the blue ropes as well. The white rabbit is somewhat annoyed, but still wants to know the answer. So he asks the white cloud: over all possible connection schemes of both the red ropes and the blue ropes, what is the total sum of the answers (that is, sum the number of assignment schemes over all red-rope and blue-rope connection schemes)? Two schemes are different if and only if there exists at least one pair of mice such that the ropes directly connecting these two mice are different in the two schemes (there are 4 possibilities for ropes between two mice: no rope directly connects them, only a red rope directly connects them, only a blue rope directly connects them, and both colors of ropes directly connect them). The white cloud cries.

This problem contains three questions: - Question 0: The shapes of two trees with $n$ nodes are given (both trees have nodes labeled from $1$ to $n$). The first tree is the red tree, and the second tree is the blue tree. You need to assign each node an integer in $[1, y]$ such that for any two nodes $p, q$, if there exists a path $(a_1 = p, a_2, \cdots , a_m = q)$ that belongs to both trees, then $p, q$ must be assigned the same number. Find the number of assignment schemes. - The definition of “there exists a path that belongs to both trees” is the same as in the “Background”. - Question 1: The blue tree is given. For all $n^{n-2}$ choices of the red tree, compute the sum of the answers to Question 0. - Question 2: For all $n^{n-2}$ choices of the blue tree, compute the sum of the answers to Question 1. Hint: There are $n^{n-2}$ different trees on $n$ nodes. In different test points, you may need to answer different questions. We use $\text{op}$ to denote the index of the question you need to answer (corresponding to 0, 1, 2 above). Since the answer may be very large, you only need to output it modulo $998, 244, 353$.

The first line contains three integers $n, y, \text{op}$ separated by spaces. If $\text{op} = 0$, then the next $2 \times (n - 1)$ lines follow: the first $(n - 1)$ lines each describe a blue rope, and the next $(n - 1)$ lines each describe a red rope. If $\text{op} = 1$, then the next $(n - 1)$ lines follow, each describing a blue rope. If $\text{op} = 2$, then there is no further input. Each rope description line contains two integers separated by a space, representing the indices of the two mice connected by this rope. The mice are numbered starting from $1$.

Output one integer, representing the answer modulo $998, 244, 353$.

#### Sample Explanation 1 The two trees are the same, so any two nodes must be assigned the same number. The number of schemes is $2$. #### Sample Explanation 2 There are three possible red trees: 1. Contains ropes $(1, 2)$ (meaning the rope connecting mice $1$ and $2$, similarly below), $(2, 3)$. Then any two mice must be assigned the same number, so the answer to Question 0 is $2$. 2. Contains ropes $(1, 2)$, $(1, 3)$. Then mice $1$ and $2$ must be assigned the same number, so the answer to Question 0 is $2 \times 2 = 4$. 3. Contains ropes $(2, 3)$, $(1, 3)$. Then node $2$ and node $3$ must be assigned the same number, so the answer to Question 0 is $2 \times 2 = 4$. Therefore, the answer to Question 1 is $2 + 4 + 4 = 10$. #### Sample Explanation 3 There are three possible blue trees. It is not hard to see that for each blue tree, the computed answer to Question 1 is $10$. So the answer is $10 \times 3 = 30$. ::cute-table{tuack} | Question Type $(\mathrm{op})$ | Test Point ID | $n$ | $y$ | Points per Test (CTT) | Points per Test (Non-CTT) | |:---:|:---:|:---:|:---:|:---:|:---:| | **0** | 1 | $\le 10$ | No special restriction | 2 | 18 | | ^ | 2 | $\le 10^{5}$ | ^ | ^ | 5 | | ^ | 3 | ^ | ^ | ^ | ^ | | **1** | 4 | $=3$ | ^ | 1 | 4 | | ^ | 5 | $=5$ | ^ | ^ | ^ | | ^ | 6 | $\le 500$ | ^ | 6 | ^ | | ^ | 7 | ^ | ^ | ^ | ^ | | ^ | 8 | $\le 5000$ | ^ | ^ | ^ | | ^ | 9 | ^ | ^ | ^ | ^ | | ^ | 10 | $\le 10^{5}$ | $=1$ | 1 | ^ | | ^ | 11 | ^ | No special restriction | 5 | 2 | | ^ | 12 | ^ | ^ | ^ | ^ | | ^ | 13 | ^ | ^ | ^ | ^ | | ^ | 14 | ^ | ^ | ^ | ^ | | **2** | 15 | $=3$ | ^ | 1 | 4 | | ^ | 16 | $=10$ | ^ | ^ | ^ | | ^ | 17 | $\le 500$ | ^ | 6 | ^ | | ^ | 18 | ^ | ^ | ^ | ^ | | ^ | 19 | $\le 5000$ | ^ | ^ | ^ | | ^ | 20 | ^ | ^ | ^ | ^ | | ^ | 21 | $\le 10^{5}$ | $=1$ | 1 | ^ | | ^ | 22 | ^ | No special restriction | 5 | 2 | | ^ | 23 | ^ | ^ | ^ | ^ | | ^ | 24 | ^ | ^ | ^ | ^ | | ^ | 25 | ^ | ^ | ^ | ^ | To optimize your reading experience, we placed the **Test Point ID** in the middle of the table; please pay attention to this. All test points satisfy $3 \leq n \leq 10^{5}, 1 \leq y