#3053. 「十二省联考 2019」希望

内存限制:1024 MiB 时间限制:3000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

题目背景

我们所可以自慰的,想来想去,也还是所谓对于将来的希望。
希望是附丽于存在的,有存在,便有希望,有希望,便是光明。

题目描述

苏拉威西。距离地球进入木星洛希极限还有 L 单位时间。

蔡德仁收到了来自艾莉芬的「点燃木星计划」。计划要求他将附近所有救援队召集到同一台转向发动机处,清除障碍,并用“春节十二响”程序操纵发动机点燃木星。

转向发动机共有 n 个,它们由 n-1 条道路相连。任意两个转向发动机都可以通过道路互相到达,二者的距离为其间最短路径的边数

附近一共部署有 k 支救援队 s_1, s_2, \dots, s_k ,每一支救援队有一个救援范围。救援范围是转向发动机集合的一个连通子集,其中任意两个发动机之间道路上的所有发动机都在救援范围中。

我们称一个发动机 u 可被救援范围为 S 的救援队到达,当且仅当 u S 中,且 S 中任意一个发动机 v u 的距离都不大于 L 。这样,无论救援队身在岗位的何处,他们都能在时间耗尽前抵达发动机 u

蔡德仁要指挥 k 支救援队集中到同一台发动机处。但由于通讯中断,蔡德仁不知道每支救援队的救援范围。他想计算出可行的调度方案数,于是将问题输入电脑。

在这台电脑的另一面——你,需要帮他统计出,在多少种可能的部署方案中存在一台能被所有救援队到达的发动机。一个方案指一组救援范围 \{S_1, S_2, \dots , S_k\} ;两个方案不同,当且仅当某个救援队 s_i 在二者中的救援范围 S_i 不同。在这次联合政府规划的饱和式救援中,两支队伍的救援范围可能相交甚至相同

你知道,答案非常大。雪地车在成千上万个地标间穿梭,可能的救援范围浩如烟海,集合所有队伍的方案却寥若晨星。但你没时间绝望,甚至没时间算出那个数字。

你只能算出答案对 998244353 取模的结果。

那就是希望。

即便需要取模,也是光明。

输入格式

从标准输入读入数据。

第一行包含三个数 n L k ,依次表示转向发动机的个数,拯救地球剩余的时间,和救援队的个数。

接下来 n-1 行,每行两个整数 u v ,表示第 u 个和第 v 个转向发动机之间有一条道路相连。

输出格式

输出到标准输出。

仅一个整数,表示方案数对 998244353 取模的结果。

样例

样例输入 1

2 1 2
1 2

样例输出 1

7

样例说明 1

一共有以下几个可行的方案:

1 号救援队      2 号救援队
{1}            {1}
{1}            {1,2}
{2}            {2}
{2}            {1,2}
{1,2}          {1}
{1,2}          {2}
{1,2}          {1,2}

样例输入 2

4 1 1
1 2
2 3
3 4

样例输出 2

9

样例说明 2

只有一个救援队,除了这个救援队的救援范围是全集 {1,2,3,4} 之外的所有方案都可行。

样例输入 3

5 1 1
1 2
1 3
2 4
2 5

样例输出 3

14

样例 4

见附加文件中 4.in4.ans

样例说明 4

这个测试点的图如下图所示:

sample4.png

样例 5

见附加文件中 5.in5.ans

数据范围与提示

测试点 n L k 是否为一条链
1 \le 16 \le n =1
2 \le 10 =2
3 =n \le 10
4 \le n
5 \le 500 =n
6 \le 10^3 \le n =1
7 \le 5\times 10^4 \le 30 \le 10
8 \le 10^5 \le 10^2 =1
9 \le 10
10 \le 10^6 \le n
11 \le 3\times 10^4 =n =1
12 \le 4\times 10^4 \le n
13 \le 5\times 10^4 \le 10
14 \le 10^5 =1
15 \le 1.5\times 10^5
16 \le 2\times 10^5 =n \le 10
17 =1
18 \le n
19 \le 10
20
21
22 \le 10^6 =1
23 \le 10
24
25

对于所有数据,有 1 \le n \le 10^6 0 \le L \le n 1 \le k \le 10

提示

请确认程序使用了文件输入输出、没有输出多余调试信息

蔡德仁抬起头。那是他从未见过的景象——木星占据了大半个天空,绚丽的色彩透过稀薄的大气,变得格外刺眼。

无边的海洋里漂流的小船,不知何时就会被狂风所倾覆;而小船上平凡的我们,也只能怀着渺茫的希望,跟随着舵手指引的航向前行吧。

他走上前按下了 Enter

$ sudo ./spring12biubiu

指令已经发出。