Small Steps
标准输入,标准输出。
对于一棵有 n 个顶点、顶点编号为 1,2,…,n 的树 t,定义 f(t) 为满足以下条件的排列 p=(p1,…,pn) 的数量:
- 对每个 i=1,2,…,n,树上连接 pi 与 pi+1 的简单路径至多包含 2 条边,其中规定 pn+1=p1。
给定正整数 N,K,以及一棵有 N 个顶点、顶点编号为 1,2,…,N 的树 T0。树的第 i 条边连接顶点 Ai 和 Bi。
将 K 个互不相交的 T0 的副本连接起来得到的树称为好树。更严格地说,一棵有 NK 个顶点、顶点编号为 1,2,…,NK 的树是好树,当且仅当:
- 对所有 1≤i≤N−1 和 0≤k≤K−1,树中都有一条连接顶点 Ai+Nk 和 Bi+Nk 的边。
求所有好树 T 的 f(T) 之和,对 998244353 取模。
共有 Q 组测试用例,请分别求解。
输入格式
第一行包含一个整数 Q。
接下来依次给出 Q 组测试用例。每组的格式如下:
N K
A_1 B_1
...
A_{N-1} B_{N-1}
当 N=1 时,该组没有描述边的行。
输出格式
输出 Q 行。第 i 行包含一个整数,表示第 i 组测试用例的答案对 998244353 取模的结果。
数据范围
- 1≤Q≤2×105;
- 1≤N≤2×105;
- 1≤K≤2×105;
- 1≤Ai<Bi≤N;
- 所有测试用例的 N 之和不超过 2×105;
- T0 是一棵树;
- 所有输入值均为整数。
题目没有限制所有测试用例的 K 之和。NK 也不要求不超过 2×105。
样例输入 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
样例说明
第一组中,任意两个顶点之间的简单路径都至多包含两条边,因此所有排列均计入答案。
第二组中,满足条件的 8 个排列为:
(1,2,4,3)、(1,3,4,2)、(2,1,3,4)、(2,4,3,1)、
(3,1,2,4)、(3,4,2,1)、(4,2,1,3)、(4,3,1,2)。
第三组需要对所有含 4 个顶点的树 T 求 f(T) 的总和。这里的 T0 没有边。
第四组中,下面两棵树都是好树的例子:
