匹配

题目描述 有一棵𝑛𝑛个点𝑛𝑛 − 1条边的树，你可以选择一个边集然后删除，一共有2𝑛𝑛−1 种删除方 法。

你想知道有多少种删除方法，使得剩下的图里面，最大匹配的大小能被𝑚𝑚整除。输 出答案对998244353取模的值。

最大匹配就是选一些边，使得每个点只和这个边集里至多一条边相连，并且边集最 大。

输入格式 第一行，两个整数𝑛𝑛, 𝑚𝑚。

接下来𝑛𝑛 − 1行，每行两个数表示一条边。

输出格式 输出一个数，表示答案。

样例输入 1 4 2 1 2 2 3 3 4

样例输出 1 3

样例输入输出 2 见下发文件。

数据规模 共 10 个测试点。

测试点1,2满足𝑛𝑛 ≤ 20。

测试点3,4满足树是一条链。

测试点5,6,7满足𝑛𝑛 ≤ 2 × 103 。

对于所有数据，满足1 ≤ 𝑛𝑛 ≤ 5 × 104 , 1 ≤ 𝑚𝑚 ≤ 200。