#P3547. [ONTAK2010]Matchings
[ONTAK2010]Matchings
[ONTAK2010] Matchings
题目描述
在一棵有 个节点的无向树上,选出一些边,使每个节点最多与一条选中的边相接。这样的一组边称为一个匹配,匹配的大小是选中的边数。
求所有匹配中的最大大小,以及达到最大大小的匹配有多少种。选中的边集合不同就算不同的方案,方案数对 取模。
输入格式
第一行一个整数 。节点编号为 到 。
接下来 行,每行两个整数 ,表示连接节点 、 的一条边。最后一行一个整数 。
输出格式
第一行输出最大匹配的大小。第二行输出达到最大大小的匹配方案数对 取模的结果。
样例 #1
5
1 2
3 2
4 5
1 4
17
2
3
数据范围
,,。