P5291 [12-Province Joint Exam 2019] Hope

What we can use to comfort ourselves, after thinking it over again and again, is still the so-called hope for the future. Hope is attached to existence. If there is existence, then there is hope. If there is hope, then there is light.

Sulawesi. There are still $L$ units of time before Earth enters Jupiter's Roche limit. Cai Deren received from Alifen the "Ignite Jupiter Plan". The plan requires him to gather all nearby rescue teams at the same steering engine, clear obstacles, and use the "Spring Festival Twelve Bangs" program to control the engine to ignite Jupiter. There are $n$ steering engines in total, connected by $n - 1$ roads. Any two steering engines can reach each other through the roads, and the distance between them is the number of edges on the shortest path between them. There are $k$ rescue teams deployed nearby: $s_1$, $s_2$, ..., $s_k$. Each rescue team has a rescue range. A rescue range is a connected subset of the set of steering engines, where for any two engines in it, all engines on the road path between them are also within the rescue range. We say an engine $u$ can be **reached** by a rescue team whose rescue range is $S$ if and only if $u$ is in $S$, and for every engine $v$ in $S$, the distance from $v$ to $u$ is **no greater than** $L$. In this way, no matter where the rescue team is within its post, they can reach engine $u$ before time runs out. Cai Deren wants to command the $k$ rescue teams to gather at the same engine. But due to communication interruption, Cai Deren does not know each rescue team's rescue range. He wants to compute the number of feasible scheduling plans, so he inputs the problem into a computer. On the other side of this computer—you need to help him count, among how many possible deployment plans there exists an engine that can be reached by all rescue teams. A **plan** refers to a set of rescue ranges $\left\{S_1, S_2, ..., S_k\right\}$. Two plans are different if and only if for some rescue team $s_i$, its rescue range $S_i$ is different in the two plans. In this saturating rescue jointly planned by the government, the rescue ranges of two teams may **intersect** or even be **the same**. You know the answer is extremely large. Snow vehicles shuttle among tens of thousands of landmarks; the possible rescue ranges are vast, yet the set of all teams' plans is like a morning star. But you have no time to despair, not even time to compute that number. You can only compute the answer modulo $998244353$. That is hope. Even if it needs to be taken modulo, it is still light.

The first line contains three numbers $n$, $L$, $k$, representing the number of steering engines, the remaining time to save Earth, and the number of rescue teams. The next $n - 1$ lines each contain two integers $u$, $v$, indicating that there is a road connecting the $u$-th and the $v$-th steering engines.

Only one integer, representing the number of plans modulo $998244353$.

#### Sample $1$ Explanation There are the following feasible plans: | Rescue Team $1$ | Rescue Team $2$ | | :---------- | :---------- | | $\texttt{\{1\}}$ | $\texttt{\{1\}}$ | | $\texttt{\{1\}}$ | $\texttt{\{1,2\}}$ | | $\texttt{\{2\}}$ | $\texttt{\{2\}}$ | | $\texttt{\{2\}}$ | $\texttt{\{1,2\}}$ | | $\texttt{\{1,2\}}$ | $\texttt{\{1\}}$ | | $\texttt{\{1,2\}}$ | $\texttt{\{2\}}$ | | $\texttt{\{1,2\}}$ | $\texttt{\{1,2\}}$ | #### Sample $2$ Explanation There is only one rescue team. All plans are feasible except the one where this rescue team's rescue range is the full set $\texttt{\{1,2,3,4\}}$. #### Sample $4$ Explanation The graph for this test point is shown in the figure below:  #### Subtasks  For all data, $1 \leqslant n \leqslant 10^6$, $0 \leqslant L \leqslant n$, $1 \leqslant k \leqslant 10$. ~~**Please confirm that your program uses file input/output and does not print extra debugging information.**~~ Cai Deren looked up. It was a scene he had never seen before—Jupiter took up most of the sky, and its brilliant colors, shining through the thin atmosphere, became especially dazzling. A small boat drifting in a boundless ocean may be overturned by a violent storm at any time; and ordinary people on the boat can only hold on to faint hope, following the heading guided by the helmsman. He stepped forward and pressed $\texttt{Enter}$. \$ sudo ./spring12biubiu The command has been issued. Translated by ChatGPT 5