#P18327. Small Steps

Small Steps

Small Steps

标准输入,标准输出。

对于一棵有 nn 个顶点、顶点编号为 1,2,…,n1,2,\ldots,n 的树 tt,定义 f(t)f(t) 为满足以下条件的排列 p=(p1,…,pn)p=(p_1,\ldots,p_n) 的数量:

  • 对每个 i=1,2,…,ni=1,2,\ldots,n,树上连接 pip_i 与 pi+1p_{i+1} 的简单路径至多包含 22 条边,其中规定 pn+1=p1p_{n+1}=p_1。

给定正整数 N,KN,K,以及一棵有 NN 个顶点、顶点编号为 1,2,…,N1,2,\ldots,N 的树 T0T_0。树的第 ii 条边连接顶点 AiA_i 和 BiB_i。

将 KK 个互不相交的 T0T_0 的副本连接起来得到的树称为好树。更严格地说,一棵有 NKNK 个顶点、顶点编号为 1,2,…,NK1,2,\ldots,NK 的树是好树,当且仅当:

  • 对所有 1≤i≤N−11\le i\le N-1 和 0≤k≤K−10\le k\le K-1,树中都有一条连接顶点 Ai+NkA_i+Nk 和 Bi+NkB_i+Nk 的边。

求所有好树 TT 的 f(T)f(T) 之和,对 998244353998244353 取模。

共有 QQ 组测试用例,请分别求解。

输入格式

第一行包含一个整数 QQ。

接下来依次给出 QQ 组测试用例。每组的格式如下:

N K
A_1 B_1
...
A_{N-1} B_{N-1}

当 N=1N=1 时,该组没有描述边的行。

输出格式

输出 QQ 行。第 ii 行包含一个整数,表示第 ii 组测试用例的答案对 998244353998244353 取模的结果。

数据范围

  • 1≤Q≤2×1051\le Q\le 2\times10^5;
  • 1≤N≤2×1051\le N\le 2\times10^5;
  • 1≤K≤2×1051\le K\le 2\times10^5;
  • 1≤Ai<Bi≤N1\le A_i<B_i\le N;
  • 所有测试用例的 NN 之和不超过 2×1052\times10^5;
  • T0T_0 是一棵树;
  • 所有输入值均为整数。

题目没有限制所有测试用例的 KK 之和。NKNK 也不要求不超过 2×1052\times10^5。

样例输入 1

5
4 1
1 2
1 3
1 4
4 1
1 2
2 3
3 4
1 4
4 2
1 2
1 3
1 4
6 200000
1 3
2 3
3 4
4 5
4 6

样例输出 1

24
8
192
2304
210217795

样例说明

第一组中,任意两个顶点之间的简单路径都至多包含两条边,因此所有排列均计入答案。

第二组中,满足条件的 88 个排列为:

(1,2,4,3)(1,2,4,3)、(1,3,4,2)(1,3,4,2)、(2,1,3,4)(2,1,3,4)、(2,4,3,1)(2,4,3,1)、 (3,1,2,4)(3,1,2,4)、(3,4,2,1)(3,4,2,1)、(4,2,1,3)(4,2,1,3)、(4,3,1,2)(4,3,1,2)。

第三组需要对所有含 44 个顶点的树 TT 求 f(T)f(T) 的总和。这里的 T0T_0 没有边。

第四组中,下面两棵树都是好树的例子:

第四组样例中的两棵好树