1724. Rikka with Match

时间限制 7000 ms   内存限制 256 MB

As we know, Rikka is poor at math. Yuta is worrying about this situation, so he gives Rikka some math tasks to practice. There is one of them:

Yuta has an undirected connected graph $G=\langle V,E \rangle$ with $n$ nodes and $n-1$ edges. Yuta can choose some edges in $E$ and remove them. It is clear that Yuta has $2^{n-1}$ different ways to remove.

Now, Yuta want to know the number of ways to remove the edges which make the maximum matching size of the remaining graph $G'$ is divisible by $m$.

It is too difficult for Rikka. Can you help her?

An edge set $S$ is a match of $G=\langle V,E \rangle$ if and only if each nodes in $V$ connects to at most one edge in $S$. The maximum matching of graph $G$ is defined as the match of $G$ with the largest size.

输入数据

The first line contains a number $t(1 \leq t \leq 100)$, the number of the testcases. And there are no more than $3$ testcases with $n > 1000$.

For each testcase, the first line contains two numbers $n,m(1 \leq n \leq 5 \times 10^4,1 \leq m \leq 200)$.

Then $n-1$ lines follow, each line contains two numbers $u,v$ which describes an edge in $G$.

输出数据

For each testcase, print a single line with a single number -- the answer modulo $998244353$.

样例输入

复制
1
4 2
1 2
2 3
3 4 \n
 · \n
 · \n
 · \n
 · \n

样例输出

复制
3 \n

提交

请先 登录

Source

2017 Multi-University Training Contest - Team 5

© 2024 FAQs Contact About