#P14956. [2026年重庆省队集训]排序大师

    ID: 14172 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>CF3000生成函数树形DP组合数学多项式动态规划数学

[2026年重庆省队集训]排序大师

给定一棵 nn 个点的树 TT,点的编号为 11 到 nn。对于值域为 [n][n] 的序列 {a1,a2,…,aℓ}\{a_1,a_2,\dots,a_\ell\},定义该序列是好的,当且仅当可以通过若干次如下操作将其排序:

  • 选择两个下标 1≤i<j≤ℓ1\leq i<j\leq \ell,满足编号为 aia_i 和 aja_j 的点在树 TT 上相邻,然后交换 aia_i 和 aja_j。

给定常数 mm,对于 ℓ\ell 从 11 到 mm,输出好的序列的个数,对 109+710^9+7 取模。

输入格式

每个测试点中包含多组测试数据。输入的第一行包含一个整数 tt,表示测试数据组数。

对于每组测试数据,输入的第一行包含两个整数 nn 和 mm。

接下来 (n−1)(n-1) 行,每行包含两个整数 uiu_i 与 viv_i,表示一条连接顶点 uiu_i 与 viv_i 的边。保证这 (n−1)(n-1) 条边构成一棵合法的树。

输出格式

对于每组测试数据,输出一行,包含 mm 个整数,表示问题的答案。

样例输入与输出

样例输入

2
3 4
1 2
2 3
4 2
1 2
1 3
3 4

样例输出

3 8 23 70
4 13

数据范围与子任务

本题开启捆绑测试。

设 N=∑nN=\sum n,M=∑mM=\sum m。对于所有数据,保证 N≤200N\leq 200,M≤105M\leq 10^5。

子任务 11(1010 分):N,M≤7N,M\leq 7。
子任务 22(1515 分):N,M≤40N,M\leq 40。
子任务 33(1515 分):N≤25N\leq 25。
子任务 44(2020 分):N≤50N\leq 50。
子任务 55(1010 分):N≤100N\leq 100。
子任务 66(3030 分):无特殊限制。