#P18472. Graph Partitioning 2

Graph Partitioning 2

Graph Partitioning 2

在成功解决《Cut Cut Cut!》之后,小青鱼想进一步提高划分图中连通块的能力。

有一天,一位神秘的智者给小青鱼一棵有 nn 个顶点的无根树,以及一个整数 kk。令 EE 为树的边集。小青鱼需要选择一个子集 E′⊆EE'\subseteq E,删除 E′E' 中的边,使剩下的每个连通块的顶点数均为 kk 或 k+1k+1。

作为分割事物的大师,小青鱼轻松解决了这个问题。但智者想知道所有可能的结果:有多少种选择 E′E' 的方式满足条件?如果选择的边子集不同,就视为不同方案。

请帮助小青鱼完成这项挑战。答案可能很大,只需输出它对 998244353998244353 取模的结果。

输入格式

有多组测试数据。第一行一个整数 TT,表示测试数据组数。对于每组测试数据:

第一行两个整数 n,kn,k(2≤n≤1052\le n\le10^5,1≤k≤n1\le k\le n),表示顶点数和较小的目标连通块大小。

接下来 n−1n-1 行,每行两个整数 ui,viu_i,v_i(1≤ui,vi≤n1\le u_i,v_i\le n),表示树的一条边。输入保证这些边构成一棵树。

保证同一输入文件所有测试数据的 nn 之和不超过 3×1053\times10^5。原题未另外给出 TT 的上限;由 n≥2n\ge2 及总限制可推出 T≤150000T\le150000。

输出格式

对每组测试数据,输出一行一个整数,表示满足条件的边子集 E′E' 的数量对 998244353998244353 取模的结果。

样例

输入:

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

输出:

2
1

样例说明

以 (u,v)(u,v) 表示连接顶点 u,vu,v 的边。第一组数据的两个合法删除边集分别为 {(2,4),(3,5)}\{(2,4),(3,5)\} 和 {(1,2),(3,5)}\{(1,2),(3,5)\}。