P16309 [ICPC 2023 Jinan R] 图划分 2

在成功解决了《Cut Cut Cut！》这道题目之后，小青鱼想要进一步提高他在划分图的连通块方面的能力。 有一天，一位神秘的智者向小青鱼提出了一个问题。在这个问题中，小青鱼被给定了一棵由 $n$ 个节点组成的无根树，以及一个整数 $k$。设 $E$ 为树中所有边的集合，小青鱼的任务是找到一个子集 $E' \subseteq E$，使得在移除 $E'$ 中的所有边后，图被划分为若干个连通块，且每个连通块的大小均为 $k$ 或 $(k+1)$。 当然，作为一位分割事物的大师，小青鱼轻松地解决了这个问题。但是神秘智者的欲望远不止于此。智者不仅想要掌握事物，还想了解所有可能的结果。因此，他要求小青鱼计算出有多少种选择 $E' \subseteq E$ 的方法满足上述条件。两种方案被视为不同的，若它们选择的边的子集不相同。 请帮助小青鱼完成这一挑战。由于答案可能很大，您只需提供答案对 $998\,244\,353$ 取模后的结果。

有多组测试数据。第一行输入一个整数 $T$ 表示测试数据组数，对于每组测试数据： 第一行输入两个整数 $n$ 和 $k$（$2 \le n \le 10^5$，$1 \le k \le n$）表示树的节点数量以及较小的连通块的目标大小。 对于接下来 $(n - 1)$ 行，第 $i$ 行输入两个整数 $u_i$ 和 $v_i$（$1 \le u_i, v_i \le n$）表示一条连接节点 $u_i$ 与 $v_i$ 的边。 保证所有数据 $n$ 之和不超过 $3 \times 10^5$。

每组数据输出一行一个整数，表示选择子集 $E'$ 的方案数对 $998\,244\,353$ 取模后的结果。

令 $(u, v)$ 表示一条连接节点 $u$ 和 $v$ 的边。对于第一组样例数据，两个合法的边的子集为 $\{(2, 4), (3, 5)\}$ 和 $\{(1, 2), (3, 5)\}$。