#P3547. [ONTAK2010]Matchings

[ONTAK2010]Matchings

[ONTAK2010] Matchings

题目描述

在一棵有 nn 个节点的无向树上,选出一些边,使每个节点最多与一条选中的边相接。这样的一组边称为一个匹配,匹配的大小是选中的边数。

求所有匹配中的最大大小,以及达到最大大小的匹配有多少种。选中的边集合不同就算不同的方案,方案数对 mm 取模。

输入格式

第一行一个整数 nn。节点编号为 11 到 nn。

接下来 n−1n-1 行,每行两个整数 a,ba,b,表示连接节点 aa、bb 的一条边。最后一行一个整数 mm。

输出格式

第一行输出最大匹配的大小。第二行输出达到最大大小的匹配方案数对 mm 取模的结果。

样例 #1

5
1 2
3 2
4 5
1 4
17
2
3

数据范围

1≤n≤15000001\le n\le1500000,1≤m≤1091\le m\le10^9,1≤a,b≤n1\le a,b\le n。