CSP1264. 剪枝（cut）

• 时限: 2000 ms | 内存: 512 MB | 难度: 9

剪枝

题目描述

小 Z 是一个辛劳的园丁，他今天要修剪一下院子里的树。
小 Z 的院子里有一个 $n$ 个点 $n - 1$ 边的树，小 Z 觉得这棵树太大了，他希望把树修剪小一点，小 Z 会剪断若干条边使得树变成若干棵小树。同时小 Z 希望每棵小树的大小都尽可能的均匀，$k$ 是小 Z 的幸运数字，他希望每棵小树的大小不小于 $k$，也不大于 $k + 1$。

小 Z 想让你帮他计算，有多少种修建方式，可以满足他的要求。由于答案可能很大，你只需提供答案对 $998\,244\, 353$ 取模后的结果。

输入格式

从 cut.in 文件读入数据。

输入包含多个测试用例。

第一行包含一个整数 $T$，表示测试用例的数量。

对于每个测试用例：

• 第一行包含两个整数 $n$ 和 $k$。

• 接下来 $(n - 1)$ 行，第 $i$ 行输入两个整数 $u_i$ 和 $v_i(1\le u_i,v_i\le n)$ 表示一条连接节点 $u_i$ 与 $v_i$ 的边。

输出格式

输出到 cut.out 文件。

对于每个测试用例，输出一行一个整数，表示所有满足条件的方案数量。

样例 #1

样例输入 #1

2
8 2
1 2
3 1
4 6
3 5
2 4
8 5
5 7
4 3
1 2
1 3
2 4

Copy

样例输出 #1

2
1

Copy

提示

【样例 1 解释】

第一组测试用例，一共只有两种方案，第一种是切断 $(2,4)$ 和 $(3,5)$,第二种是切断 $(1,2)$ 和 $(3,5)$。

第二组测试用例，唯一的方案是什么都不剪断。

样例 2～ 5 都可以点击链接 cut_sample.zip 下载大样例压缩包，具体如下。

【样例 2】

见附件的 cut_sample2.in 与 cut_sample2.ans。

【样例 3】

见附件的 cut_sample3.in 与 cut_sample3.ans。

【样例 4】

见附件的 cut_sample4.in 与 cut_sample4.ans。

【样例 5】

见附件的 cut_sample5.in 与 cut_sample5.ans。

【数据范围】

对于 $20\%$ 的数据，满足 $1\le n,k \le 20$；

对于 $40\%$ 的数据，满足 $1\le n,k \le 5000$；

另有 $10\%$ 的数据，满足特殊性质 A;

另有 $10\%$ 的数据，满足特殊性质 B;

对于 $100\%$ 的数据，满足 $2\le n\le 10^5,1\le k \le n$，保证所有测试用例中 $n$ 的总和不超过 $3\times10^5$。

• 特殊性质 A: 对于任意的 $i(1\le i \le n - 1)$，都有 $u_i = i,v_i = i + 1$。

• 特殊性质 B: 对于任意的 $i(1\le i \le n - 1)$，都有 $u_i = 1,v_i = i + 1$。