CF981H.K Paths

You are given a tree of $n$ vertices. You are to select $k$ (not necessarily distinct) simple paths in such a way that it is possible to split all edges of the tree into three sets: edges not contained in any path, edges that are a part of exactly one of these paths, and edges that are parts of all selected paths, and the latter set should be non-empty.

Compute the number of ways to select $k$ paths modulo $998244353$.

The paths are enumerated, in other words, two ways are considered distinct if there are such $i$ ($1 \leq i \leq k$) and an edge that the $i$-th path contains the edge in one way and does not contain it in the other.

给你一棵包含 $n$ 个顶点的树。你需要选择 $k$ 条（不一定互不相同）简单路径，使得可以将树的所有边划分为如下三类：

• 不属于任何一条所选路径的边；
• 恰好属于所选路径中某一条的边；
• 属于所有所选路径的边（即这 $k$ 条路径的公共边），且该类边集非空。

请计算满足条件的 $k$ 条路径的选择方案数，对 $998244353$ 取模。

路径是有编号的，即：若存在某个 $i$（$1 \leq i \leq k$）以及某条边，使得在一种方案中第 $i$ 条路径包含该边、而在另一种方案中不包含，则这两种方案被视为不同。

The first line contains two integers $n$ and $k$ ($1 \leq n, k \leq 10^{5}$) — the number of vertices in the tree and the desired number of paths.

The next $n - 1$ lines describe edges of the tree. Each line contains two integers $a$ and $b$ ($1 \le a, b \le n$, $a \ne b$) — the endpoints of an edge. It is guaranteed that the given edges form a tree.

第一行包含两个整数 $n$ 和 $k$（$1 \leq n, k \leq 10^{5}$）—— 分别表示树中顶点的数量和期望的路径数量。

接下来的 $n - 1$ 行描述树的边。每行包含两个整数 $a$ 和 $b$（$1 \le a, b \le n$，$a \ne b$）—— 表示一条边的两个端点。保证所给的边构成一棵树。

Print the number of ways to select $k$ enumerated not necessarily distinct simple paths in such a way that for each edge either it is not contained in any path, or it is contained in exactly one path, or it is contained in all $k$ paths, and the intersection of all paths is non-empty.

As the answer can be large, print it modulo $998244353$.

输出满足以下条件的选取 $k$ 条（带编号、不一定互异）简单路径的方法数：对每条边，它要么不被任何路径包含，要么恰好被其中一条路径包含，要么被全部 $k$ 条路径包含；且这 $k$ 条路径的交集非空。

由于答案可能很大，请对 $998244353$ 取模后输出。

In the first example the following ways are valid：

• $((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))$.

In the second example $k=1$, so all $n \cdot (n - 1) / 2 = 5 \cdot 4 / 2 = 10$ paths are valid.

In the third example, the answer is $\geq 998244353$, so it was taken modulo $998244353$, don't forget it!

在第一个例子中，以下方案是合法的：

• $((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$ 取模，请勿遗漏！