AT_tupc2024_i.Small Steps

对于一个包含 $n$ 个顶点、顶点编号为 $1$ 到 $n$ 的树 $t$，我们定义满足下列条件的排列 $p = (p_1, \dots, p_n)$（$p$ 是 $(1, \dots, n)$ 的一个排列）有多少个，记作 $f(t)$。

• 对于 $i = 1, \dots, n$，连接顶点 $p_i$ 和顶点 $p_{i+1}$ 的最短简单路径所经过的边数不超过 $2$（这里规定 $p_{n+1} = p_1$）。

---

给定正整数 $N, K$ 以及顶点编号为 $1$ 到 $N$ 的 $N$ 个顶点的树 $T_0$。$T_0$ 的第 $i$ 条边连接顶点 $A_i$ 和顶点 $B_i$。

将 $K$ 个 $T_0$ 连接起来所得的树称为好树。更为正式地说，当且仅当顶点编号为 $1$ 到 $NK$ 的 $NK$ 个顶点的树 $T$ 满足以下条件时，$T$ 是好树：

• 对于所有满足 $1 \le i \le N-1$ 且 $0 \le k \le K-1$ 的整数对 $(i, k)$，$T$ 包含一条边连接顶点 $(A_i + N\times k)$ 和顶点 $(B_i + N\times k)$。

请你求出所有好树 $T$ 的 $f(T)$ 之和对 $998244353$ 取模的结果。

有 $Q$ 组测试数据，请你分别输出答案。

输入以如下格式从标准输入读入。

$Q$
$\mathrm{case}_1$
$\vdots$
$\mathrm{case}_Q$

每组 $\mathrm{case}_i$ 输入格式如下：

$N$ $K$
$A_1$ $B_1$
$\vdots$
$A_{N-1}$ $B_{N-1}$

输出共 $Q$ 行。第 $i$ 行输出第 $i$ 组测试数据的答案。

样例说明 1

对于第 1 个测试点，由于所有简单路径都只包含至多 2 条边，因此所有可能的排列均被计数。

对于第 2 个测试点，被计数的排列共有 $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)$。

对于第 3 个测试点，需要求所有 $4$ 个顶点的树 $T$ 的 $f(T)$ 的总和。注意 $T_0$ 可能不含任何边。

对于第 4 个测试点，作为好树的例子，如下图所示：

数据范围

• $1\le Q\le 2\times 10 ^ 5$
• $1\le N\le 2\times 10 ^ 5$
• $1\le K\le 2\times 10 ^ 5$
• $1\le A_i < B_i \le N$
• 所有输入文件中 $N$ 的总和不超过 $2\times 10^5$
• 输入给定的图均为树
• 输入全部为整数

由 ChatGPT 5 翻译