白兔喜欢树。
白云喜欢数数。
有
白云要给予每只鼠一个数。这个数可以是
白兔给了白云一个要求:对于两只鼠
白云想知道,她有多少种给予数的方案呢?
鼠在不停地挣扎,想要摆脱绳子的束缚。白云还没有思考出来,鼠便把红色绳子都咬断了。
白兔有些气恼,但是他还是想要知道答案。他便问白云:对于所有红色绳子的连接方案,答案的总和(即求所有红色绳子连接方案的给予数方案之和)是多少?
鼠在不停地挣扎,想要摆脱绳子的束缚。白云还没有思考出来,鼠便把蓝色绳子也咬断了。
白兔有些气恼,但是他还是想要知道答案。他便问白云:对于所有红色和蓝色绳子的连接方案,答案的总和(即求所有红色和蓝色绳子连接方案的给予数方案之和)是多少?两个方案不同当且仅当存在至少一对鼠,在两种方案中,这两只鼠之间直接连接的绳子不同(两只鼠之间连接绳子的可能性有 4 种:没有绳子直接连接,只有红色绳子直接连接,只有蓝色绳子直接连接,两种颜色的绳子均直接连接)。
白云哭了。
题目描述
本题包含三个问题:
- 问题 0:已知两棵
个节点的树的形态(两棵树的节点标号均为 至 ),其中第一棵树是红树,第二棵树是蓝树。要给予每个节点一个 中的整数,使得对于任意两个节点 ,如果存在一条路径 同时属于这两棵树,则 必须被给予相同的数。求给予数的方案数。- 存在一条路径同时属于这两棵树的定义见「题目背景」。
- 问题 1:已知蓝树,对于红树的所有
种选择方案,求问题 0 的答案之和。 - 问题 2:对于蓝树的所有
种选择方案,求问题 1 的答案之和。
提示:
在不同的测试点中,你将可能需要回答不同的问题。我们将用
由于答案可能很大,因此你只需要输出答案对
输入格式
从标准输入中读入数据。
第一行三个用空格隔开的整数
如果
如果
如果
描述绳子的各行将包含两个用空格隔开的整数,分别表示被这条绳子连接的两只鼠的编号。鼠的编号是从
输出格式
输出到标准输出中。
输出一个整数,表示答案对
样例一
input
3 2 0 1 2 2 3 1 2 2 3
output
2
explanation
两棵树相同,所以任意两个点都必须被给予相同的数,方案数为
样例二
input
3 2 1 1 2 2 3
output
10
explanation
红树共有三种可能的情况:
1. 包含绳子
综上,问题 1 的答案为
样例三
input
3 2 2
output
30
explanation
蓝树一共有三种可能的情况。不难发现,对于蓝树的每一种情况,求得的问题 1 的答案都是
样例四至样例六
见样例数据下载。
限制与约定
对于所有测试数据:
问题类型 | 测试点编号 | 集训队每个测试点分值 | 非集训队每个测试点分值 | ||
---|---|---|---|---|---|
0 | 1 | | 无特殊限制 | 2 | 18 |
0 | 2 | | 无特殊限制 | 2 | 5 |
0 | 3 | | 无特殊限制 | 2 | 5 |
1 | 4 | | 无特殊限制 | 1 | 4 |
1 | 5 | | 无特殊限制 | 1 | 4 |
1 | 6 | | 无特殊限制 | 6 | 4 |
1 | 7 | | 无特殊限制 | 6 | 4 |
1 | 8 | | 无特殊限制 | 6 | 4 |
1 | 9 | | 无特殊限制 | 6 | 4 |
1 | 10 | | | 1 | 4 |
1 | 11 | | 无特殊限制 | 5 | 2 |
1 | 12 | | 无特殊限制 | 5 | 2 |
1 | 13 | | 无特殊限制 | 5 | 2 |
1 | 14 | | 无特殊限制 | 5 | 2 |
2 | 15 | | 无特殊限制 | 1 | 4 |
2 | 16 | | 无特殊限制 | 1 | 4 |
2 | 17 | | 无特殊限制 | 6 | 4 |
2 | 18 | | 无特殊限制 | 6 | 4 |
2 | 19 | | 无特殊限制 | 6 | 4 |
2 | 20 | | 无特殊限制 | 6 | 4 |
2 | 21 | | | 1 | 4 |
2 | 22 | | 无特殊限制 | 5 | 2 |
2 | 23 | | 无特殊限制 | 5 | 2 |
2 | 24 | | 无特殊限制 | 5 | 2 |
2 | 25 | | 无特殊限制 | 5 | 2 |
为了优化你的阅读体验,我们把测试点编号放在了表格的中间,请注意这一点。
在 UOJ 上,提交的程序将按照「集训队每个测试点分值」一栏的分值进行评分。
时间限制: 4s
空间限制: 512MB