K 条路径

• 时间限制：5 秒
• 内存限制：256 MiB

题目描述

给定一棵有 $n$ 个顶点的树。你需要选择 $k$ 条简单路径，这些路径不必互不相同。

对树上的每条边，统计它被所选路径包含的次数。要求每条边的次数只能是 $0$、$1$ 或 $k$，并且至少有一条边的次数为 $k$。

求满足条件的有序路径组数量，答案对 $998244353$ 取模。路径组是有序的：只要存在一个编号对应的路径不同，两种方案就不同。每条路径连接两个不同的顶点，路径两个端点的先后顺序不作区分。

输入格式

第一行包含两个整数 $n,k$，分别表示顶点数和路径数。

接下来 $n-1$ 行，每行包含两个整数 $u,v$，表示树上有一条连接顶点 $u$ 与顶点 $v$ 的边。

输出格式

输出一个整数，表示满足条件的有序路径组数量对 $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\le n,k\le10^5$，输入边构成一棵树。