Logo Universal Online Judge

UOJ

时间限制:2 s 空间限制:512 MB
统计

【题目描述】
给定一棵 n 个结点的树,你需要为每个结点确定一个等级,满足下列条件:
• 每个结点的等级是一个不超过 k 的正整数。
• 在任意两个等级相同的结点之间的路径上,必须存在等级严格更高的结点。
你并不关心如何分级,只想知道有多少种合法分级的方案,请你求出合法分级的方 案数对 998244353 取模后的结果。
【输入格式】
从文件 tree.in 中读入数据。
第一行两个整数 n, k。
接下来 n − 1 行,每行两个正整数 u, v 表示存在一条 u, v 之间的边。
保证输入的是一棵树。
【输出格式】
输出到文件 tree.out 中。
一行一个整数表示方案数对 998244353 取模后的结果。
【样例 1 输入】

4 2
1 2
1 3
1 4
【样例 1 输出】

1
【样例 1 解释】
唯一一种合法的分级方案是给结点 2, 3, 4 都赋为等级 1,结点 1 赋为等级 2。
【样例 2、3】
见 /ex_tree2.in,/ex_tree3.in 与 /ex_tree2.out,/ex_tree3.out。
样例 2、3
【测试点约束】
对于所有测试点:$1 ≤ n ≤ 50,1 ≤ k ≤ 17$。
每个测试点的具体限制见下表:

测试点编号 n ≤ k ≤
1 ∼ 2 4 4
3 ∼ 6 7 7
7 ∼ 10 50 8
11 ∼ 14 50 15
15 ∼ 20 50 17