2492: 希望(hope)

Memory Limit:1500 MB Time Limit:5.000 S
Judge Style:Text Compare Creator:
Submit:27 Solved:6

Description

【题目背景】
我们所可以自慰的,想来想去,也还是所谓对于将来的希望。
希望是附丽于存在的,有存在,便有希望,有希望,便是光明。
【题目描述】
苏拉威西。距离地球进入木星洛希极限还有 L 单位时间。
蔡德仁收到了来自艾莉芬的“点燃木星计划”。计划要求他将附近所有救援队召集
到同一台转向发动机处,清除障碍,并用“春节十二响”程序操纵发动机点燃木星。
转向发动机共有 n 个,它们由 n 1 条道路相连。任意两个转向发动机都可以通过
道路互相到达,二者的距离为其间最短路径的. .
附近一共部署有 k 支救援队 s1, s2, . . . , sk,每一支救援队有一个救援范围。救援范
围是转向发动机集合的一个连通子集,其中任意两个发动机之间道路上的所有发动机
都在救援范围中。
我们称一个发动机 u 可被救援范围为 S 的救援队. . ,当且仅当 u S 中,且 S
中任意一个发动机 v u 的距离都. . . L。这样,无论救援队身在岗位的何处,他
们都能在时间耗尽前抵达发动机 u
蔡德仁要指挥 k 支救援队集中到同一台发动机处。但由于通讯中断,蔡德仁不知
道每支救援队的救援范围。他想计算出可行的调度方案数,于是将问题输入电脑。
在这台电脑的另一面——你,需要帮他统计出,在多少种可能的部署方案中存在一
台能被所有救援队到达的发动机。一个. . 指一组救援范围 {S 1, S 2, . . . , S k};两个方案
不同,当且仅当某个救援队 si 在二者中的救援范围 S i 不同。在这次联合政府规划的
饱和式救援中,两支队伍的救援范围可能. . 甚至. .
你知道,答案非常大。雪地车在成千上万个地标间穿梭,可能的救援范围浩如烟
海,集合所有队伍的方案却寥若晨星。但你没时间绝望,甚至没时间算出那个数字。
你只能算出答案对 998244353 取模的结果。
那就是希望。
即便需要取模,也是光明。

Input

从文件 hope.in 中读入数据。
第一行包含三个数 nLk,依次表示转向发动机的个数,拯救地球剩余的时间,和救援队的个数。
接下来 n 1 行,每行两个整数 uv,表示第 u 个和第 v 个转向发动机之间有一条道路相连。

Output

输出到文件 hope.out 中。
仅一个整数,表示方案数对 998244353 取模的结果。

Sample Input Copy

2 1 2 
1 2
【样例 2 输入】
4 1 1
1 2
2 3
3 4
【样例 3 输入】
5 1 1
1 2
1 3
2 4
2 5

Sample Output Copy

7
【样例 2 输出】
9
【样例 3 输出】
14

HINT

【样例 1 解释】
一共有以下几个可行的方案:
1 号救援队 2 号救援队
{1} {1}
{1} {1,2}
{2} {2}
{2} {1,2}
{1,2} {1}
{1,2} {2}
{1,2} {1,2}
【样例 2 解释】
只有一个救援队,除了这个救援队的救援范围是全集 {1,2,3,4} 之外的所有方案
都可行。
对于所有数据,有 1 n 1060 L n1 k 10
【提示】
. . . . . 使. . . . . . . . 出、. . . . . . . . . . .
蔡德仁抬起头。那是他从未见过的景象——木星占据了大半个天空,绚丽的色彩透过稀薄的大气,变得格外刺眼。
无边的海洋里漂流的小船,不知何时就会被狂风所倾覆;而小船上平凡的我们,也只能怀着渺茫的希望,跟随着舵手指引的航向前行吧。
他走上前按下了 Enter
$ sudo ./spring12biubiu
指令已经发出。

Source/Category