CF981H K Paths

给定一棵有 $n$ 个顶点的树。你需要选择 $k$ 条（不一定不同的）简单路径，使得可以将树的所有边分为三类：未被任何路径包含的边、恰好被一条路径包含的边、被所有选定路径都包含的边，并且最后一类（即被所有路径都包含的边）必须非空。 计算有多少种方式可以选择 $k$ 条有序的简单路径，答案对 $998244353$ 取模。 路径是有序的，也就是说，如果存在某个 $i$（$1 \leq i \leq k$）和一条边，使得第 $i$ 条路径在一种方案中包含该边，而在另一种方案中不包含该边，则这两种方案被认为是不同的。

第一行包含两个整数 $n$ 和 $k$（$1 \leq n, k \leq 10^{5}$），分别表示树的顶点数和要选择的路径数。 接下来的 $n-1$ 行描述树的边。每行包含两个整数 $a$ 和 $b$（$1 \leq a, b \leq n$，$a \ne b$），表示一条连接顶点 $a$ 和 $b$ 的边。保证给定的边构成一棵树。

输出选择 $k$ 条有序（不一定不同）简单路径的方案数，使得每条边要么未被任何路径包含，要么恰好被一条路径包含，要么被所有 $k$ 条路径都包含，并且被所有路径都包含的边集合非空。答案对 $998244353$ 取模。

在第一个样例中，以下方案是合法的： - $((1,2), (1,2))$， - $((1,2), (1,3))$， - $((1,3), (1,2))$， - $((1,3), (1,3))$， - $((1,3), (2,3))$， - $((2,3), (1,3))$， - $((2,3), (2,3))$。 在第二个样例中，$k=1$，所以所有 $n \cdot (n - 1) / 2 = 5 \cdot 4 / 2 = 10$ 条路径都是合法的。 在第三个样例中，答案 $\geq 998244353$，所以要对 $998244353$ 取模，不要忘记！ 由 ChatGPT 4.1 翻译