P16309 [ICPC 2023 Jinan R] Graph Partition 2

After successfully solving the problem *Cut Cut Cut!*, Xiaoqingyu wants to further improve his ability to partition a graph into connected components. One day, a mysterious wise man asked Xiaoqingyu a question. In this problem, Xiaoqingyu is given an unrooted tree with $n$ nodes and an integer $k$. Let $E$ be the set of all edges in the tree. Xiaoqingyu needs to find a subset $E' \subseteq E$ such that after removing all edges in $E'$, the graph is split into several connected components, and the size of each connected component is either $k$ or $(k+1)$. Of course, as a master of splitting things, Xiaoqingyu solved this problem easily. But the wise man wanted more than that. He not only wanted to find one solution, but also to know all possible results. Therefore, he asked Xiaoqingyu to compute how many ways there are to choose $E' \subseteq E$ that satisfy the condition above. Two solutions are considered different if the chosen edge subsets are different. Please help Xiaoqingyu complete this challenge. Since the answer may be very large, you only need to output the result modulo $998\,244\,353$.

There are multiple testcases. The first line contains an integer $T$ denoting the number of testcases. For each testcase: The first line contains two integers $n$ and $k$ ($2 \le n \le 10^5$, $1 \le k \le n$), representing the number of nodes in the tree and the target size of the smaller connected components. In the next $(n - 1)$ lines, the $i$-th line contains two integers $u_i$ and $v_i$ ($1 \le u_i, v_i \le n$), representing an edge connecting nodes $u_i$ and $v_i$. It is guaranteed that the sum of $n$ over all testcases does not exceed $3 \times 10^5$.

For each testcase, output one line containing one integer, representing the number of ways to choose the subset $E'$ modulo $998\,244\,353$.

Let $(u, v)$ denote an edge connecting nodes $u$ and $v$. For the first sample, two valid edge subsets are $\{(2, 4), (3, 5)\}$ and $\{(1, 2), (3, 5)\}$. Translated by ChatGPT 5