#2983. 「WC2019」数树

内存限制:512 MiB 时间限制:4000 ms 输入文件: tree.in 输出文件: tree.out
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

题目背景

白兔喜欢树。

白云喜欢数数。

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

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

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

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

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

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

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

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

白云哭了。

题目描述

本题包含三个问题:

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

提示:nn 个节点的树一共有 nn2n^{n−2} 种。

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

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

输入格式

从文件 tree.in 中读入数据。

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

输出格式

输出到文件 tree.out 中。

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

样例

样例输入 1

3 2 0
1 2
2 3
1 2
2 3

样例输出 1

2

样例说明 1

两棵树相同,所以任意两个点都必须被给予相同的数,方案数为 22

样例输入 2

3 2 1
1 2
2 3

样例输出 2

10

样例说明 2

红树共有三种可能的情况:

  1. 包含绳子 (1,2)(1, 2)(表示连接 1,21, 2 号鼠的绳子,下同)、(2,3)(2, 3):此时任意两只鼠都必须被给予相同的数,问题 0 的答案为 22
  2. 包含绳子 (1,2)(1, 2)(1,3)(1, 3):此时 11 号鼠和 22 号鼠必须被给予相同的数,问题 0 的答案为 2×2=42 \times 2 = 4
  3. 包含绳子 (2,3)(2, 3)(1,3)(1, 3):此时 22 号点和 33 号点必须被给予相同的数,问题 0 的答案为 2×2=42 \times 2 = 4

综上,问题 1 的答案为 2+4+4=102 + 4 + 4 = 10

样例输入 3

3 2 2

样例输出 3

30

样例说明 3

蓝树一共有三种可能的情况。不难发现,对于蓝树的每一种情况,求得的问题 1 的答案都是 1010。所以答案为 10×3=3010 \times 3 = 30

样例 4, 5, 6

见附加文件

数据范围与提示

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

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

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

在 LibreOJ 上,提交的程序将按照「集训队每个测试点分值」一栏的分值进行评分。