A85843.「WC2019」数树

题目背景

白兔喜欢树。

白云喜欢数数。

有 $n$ 只鼠，白兔用 $n − 1$ 根蓝色绳子把它们连成了一棵树，每根蓝色绳子连着两只鼠，白云用 $n − 1$ 根红色绳子把它们连成了一棵树，每根红色绳子连接着两只鼠。

白云要给予每只鼠一个数。这个数可以是 $[1, y]$ 中的任意一个整数。

白兔给了白云一个要求：对于两只鼠 $p, q$，若存在一条连接这两只鼠的路径同时属于这两棵树，则 $p$ 和 $q$ 必须被给予相同的整数。存在一条路径同时属于这两棵树指的是：存在一个序列 $(a_1 = p, a_2, \cdots , a_m = q)$，使得：对于所有 $i \in [1, m − 1]$，都有 $a_i$ 和 $a_{i+1}$ 既有一根红色绳子直接相连也有一根蓝色绳子直接相连。

白云想知道，她有多少种给予数的方案呢？

鼠在不停地挣扎，想要摆脱绳子的束缚。白云还没有思考出来，鼠便把红色绳子都咬断了。

白兔有些气恼，但是他还是想要知道答案。他便问白云：对于所有红色绳子的连接方案，答案的总和（即求所有红色绳子连接方案的给予数方案之和）是多少？

鼠在不停地挣扎，想要摆脱绳子的束缚。白云还没有思考出来，鼠便把蓝色绳子也咬断了。

白兔有些气恼，但是他还是想要知道答案。他便问白云：对于所有红色和蓝色绳子的连接方案，答案的总和（即求所有红色和蓝色绳子连接方案的给予数方案之和）是多少？两个方案不同当且仅当存在至少一对鼠，在两种方案中，这两只鼠之间直接连接的绳子不同（两只鼠之间连接绳子的可能性有 4 种：没有绳子直接连接，只有红色绳子直接连接，只有蓝色绳子直接连接，两种颜色的绳子均直接连接）。

白云哭了。

题目描述

本题包含三个问题：

• 问题 0：已知两棵 $n$ 个节点的树的形态（两棵树的节点标号均为 $1$ 至 $n$），其中第一棵树是红树，第二棵树是蓝树。要给予每个节点一个 $[1, y]$ 中的整数，使得对于任意两个节点 $p, q$，如果存在一条路径 $(a_1 = p, a_2, \cdots , a_m = q)$ 同时属于这两棵树，则 $p, q$ 必须被给予相同的数。求给予数的方案数。
  • 存在一条路径同时属于这两棵树的定义见「题目背景」。
• 问题 1：已知蓝树，对于红树的所有 $n^{n−2}$ 种选择方案，求问题 0 的答案之和。
• 问题 2：对于蓝树的所有 $n^{n−2}$ 种选择方案，求问题 1 的答案之和。

提示：$n$ 个节点的树一共有 $n^{n−2}$ 种。

在不同的测试点中，你将可能需要回答不同的问题。我们将用 $\text{op}$ 来指代你需要回答的问题编号（对应上述 0、 1、 2）。

由于答案可能很大，因此你只需要输出答案对 $998, 244, 353$ 取模的结果即可。

第一行三个用空格隔开的整数 $n, y, \text{op}$。
如果 $\text{op} = 0$，则接下来 $2 \times (n − 1)$ 行，前 $(n − 1)$ 行每描述一条蓝色绳子，接下来 $(n − 1)$ 行每行描述一条红色绳子。
如果 $\text{op} = 1$，则接下来 $(n − 1)$ 行，每行描述一条蓝色绳子。
如果 $\text{op} = 2$，则接下来没有输入。
描述绳子的各行将包含两个用空格隔开的整数，分别表示被这条绳子连接的两只鼠的编号。鼠的编号是从 $1$ 开始的。

输出一个整数，表示答案对 $998, 244, 353$ 取模的结果。

问题类型 $(\text{op}=)$	测试点编号	$n$	$y$	集训队每个测试点分值	非集训队每个测试点分值
0	1	$\le 10$	无特殊限制	2	18
0	2	$\le 10^5$	无特殊限制	2	5
0	3	$\le 10^5$	无特殊限制	2	5
1	4	$=3$	无特殊限制	1	4
1	5	$=5$	无特殊限制	1	4
1	6	$\le 500$	无特殊限制	6	4
1	7	$\le 500$	无特殊限制	6	4
1	8	$\le 5000$	无特殊限制	6	4
1	9	$\le 5000$	无特殊限制	6	4
1	10	$\le 10^5$	$=1$	1	4
1	11	$\le 10^5$	无特殊限制	5	2
1	12	$\le 10^5$	无特殊限制	5	2
1	13	$\le 10^5$	无特殊限制	5	2
1	14	$\le 10^5$	无特殊限制	5	2
2	15	$=3$	无特殊限制	1	4
2	16	$=10$	无特殊限制	1	4
2	17	$\le 500$	无特殊限制	6	4
2	18	$\le 500$	无特殊限制	6	4
2	19	$\le 5000$	无特殊限制	6	4
2	20	$\le 5000$	无特殊限制	6	4
2	21	$\le 10^5$	$=1$	1	4
2	22	$\le 10^5$	无特殊限制	5	2
2	23	$\le 10^5$	无特殊限制	5	2
2	24	$\le 10^5$	无特殊限制	5	2
2	25	$\le 10^5$	无特殊限制	5	2

为了优化你的阅读体验，我们把测试点编号放在了表格的中间，请注意这一点。

所有测试点均满足 $3 \le n \le 10^5， 1 \le y \lt 998244353， \text{op} \in \{0, 1, 2\}$。