← 返回题目列表

Codeforces · 981/H

H. K 路径

中文机器翻译题面 查看原题

给你一棵有 $$$n$$$ 个顶点的树。您将选择 $$$k$$$ (不一定不同)简单路径,以便可以将树的所有边分为三组:不包含在任何路径中的边、恰好属于这些路径之一的边、以及属于所有选定路径的部分的边,并且后一组应该是非空的。

计算以 $$$998244353$$$ 为模选择 $$$k$$$ 路径的方式数。

路径被枚举,换句话说,如果存在这样的 $$$i$$$ ($$$1 \leq i \leq k$$$) 和第 $$$i$$$ 路径在一种方式中包含该边而在另一种方式中不包含它的边,则认为两种方式是不同的。

输入

第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \leq n, k \leq 10^{5}$$$) - 树中的顶点数和所需的路径数。

接下来的 $$$n - 1$$$ 行描述树的边缘。每行包含两个整数 $$$a$$$ 和 $$$b$$$ ($$$1 \le a, b \le n$$$, $$$a \ne b$$$) — 边的端点。保证给定的边形成一棵树。

输出

打印选择 $$$k$$$ 的方法数量,枚举不一定是不同的简单路径,对于每条边,要么不包含在任何路径中,要么只包含在一个路径中,要么包含在所有 $$$k$$$ 路径中,并且所有路径的交集非空。

由于答案可能很大,请打印 $$$998244353$$$ 的模。

示例

输入 #1

3 2
1 2
2 3

输出 #1

7

输入 #2

5 1
4 1
2 3
4 5
2 1

输出 #2

10

输入 #3

29 29
1 2
1 3
1 4
1 5
5 6
5 7
5 8
8 9
8 10
8 11
11 12
11 13
11 14
14 15
14 16
14 17
17 18
17 19
17 20
20 21
20 22
20 23
23 24
23 25
23 26
26 27
26 28
26 29

输出 #3

125580756

注意

在第一个示例中,以下方式是有效的:

- $$$((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$$$取模,不要忘记!