#P4455. [Zjoi2016]小星星

    ID: 3660 传统题 2000ms 512MiB 尝试: 1200 已通过: 521 难度: 8 上传者: 标签>难度分类提高+/省选-组合数学容斥原理动态规划树形 DP枚举与搜索全子集枚举模拟与实现技巧高精度加法高精度乘法CF2400

[Zjoi2016]小星星

题目描述

小 Y 做了一件由 nn 颗小星星和 mm 条彩色细线组成的饰品,每条细线连接两颗小星星。有一天,饰品上的许多细线被拆掉了,只剩下 n−1n-1 条线,但这 nn 颗小星星仍然连通,形成了一棵树。

小 Y 找到了饰品原来的设计图。她想把现在的 nn 颗小星星和图纸上的 nn 颗小星星一一对应。若现在的两颗小星星有细线相连,它们对应的图纸上的两颗小星星也必须有细线相连。请计算有多少种满足条件的对应方式。

输入格式

第一行输入两个正整数 n,mn,m,分别表示原饰品的小星星数和细线数。两套编号均为 11 到 nn。

接下来 mm 行,每行输入两个正整数 u,vu,v,表示原饰品上连接 uu 和 vv 的一条细线。保证 u≠vu\ne v,且每对小星星之间最多只有一条细线。

接下来 n−1n-1 行,每行输入两个正整数 u,vu,v,表示现有饰品上的一条细线。保证现有饰品是连通的。

输出格式

输出一行一个整数,表示有效对应方式的数量。如果不存在有效的对应方式,输出 0。

样例 1

4 3
1 2
1 3
1 4
4 1
4 2
4 3
6

样例 1 说明

现有饰品的第 44 颗小星星必须对应原图纸的第 11 颗。现在的第 1,2,31,2,3 颗可按任意顺序对应原图纸的第 2,3,42,3,4 颗,共有 3!=63!=6 种方式。

样例 2

10 23
3 4
10 1
1 2
3 2
5 3
9 6
7 1
8 4
10 2
6 5
5 9
7 3
9 3
7 8
8 9
4 7
8 10
9 1
8 5
6 8
8 2
9 10
3 6
4 3
5 4
1 2
10 9
6 2
1 3
8 5
2 9
7 6
2968

数据规模与约定

n≤17n\le 17,m≤n(n−1)2m\le \dfrac{n(n-1)}{2}。

测试点 nn 特殊约定
1,21,2 1010 无
3,43,4 1717 现有饰品中每颗小星星至多与另外两颗小星星相连
5,65,6 1414 无
77 1616 答案不超过 10510^5
88 无
9,109,10 1717