Background

Looking back on this old street, in the mist and clouds I trace who I am.
Just a few drops of evening rain are enough to cover up right and wrong.
When the moonlight surges, who will gently knock on this door?
Moss-green bluestone slabs, mottled with years flowing like water.
A few small cups of wine, yet the tangled knot cannot be sorted out.
In your indifferent brows, I glimpse the joys and sorrows of those who part, frosted by snow.

Luo Tianyi sees a pear tree in the snow. There is limited energy in the root of the pear tree, and it can transmit energy upward to other nodes. But the wind and snow are heavy: at every moment, the energy at each node may increase or decrease, and nodes with too little energy will fall off.

Problem Description

Specifically, this pear tree can be abstracted as a tree rooted at node $1$. Initially, every node is white. Each node has energy $a_i$. Initially, the energy of all nodes except $1$ is $0$, and $a_1=k$. We define an accumulated energy $b$.

We define the value of a sequence $\{v_t\}$ through the following process:

• Pass through the $t$ moments $1,2,3,\dots,t$ in increasing order.
• At moment $x$, perform $b\gets b+v_x$.
• For an edge $(u,v)$ in the tree, with $u$ as the parent, you may choose an integer $h\in[0,a_u]$ and perform $a_u\gets a_u-h$, $a_v\gets a_v+h$. After that, within this moment, edges of the form $(v,w)$ where $v$ is the parent cannot be operated on.
• If a node $i$ satisfies $a_i+b<0$, dye node $i$ and all nodes in the subtree of $i$ black.
• Perform optimal operations to maximize the number of white nodes after moment $t$. The value of this sequence is this maximum number of white nodes.

A sequence $\{v_t\}$ is defined to be valid if and only if $\forall i\in[1,t]$, $\lvert v_i\rvert\in[0,m]$. Given $t$, compute the sum of the values of all valid sequences $\{v_t\}$ modulo $998244353$.

Input Format

The first line contains four non-negative integers $n,m,t,k$, representing the number of nodes in the tree, the range of values of $v_i$, the number of moments, and the initial value of $a_1$, respectively.

The next $n-1$ lines each contain two positive integers $u,v$, indicating that there is an edge between node $u$ and node $v$.

Output Format

Output the sum of the values of all valid sequences modulo $998244353$.

1 1 1 1

3

3 1 2 2
1 2
1 3

22

5 2 3 5
1 2
2 3
2 4
4 5

407

10 5 6 44
1 2
1 3
2 5
2 6
3 4
6 7
6 8
4 9
9 10

10465095

Hint

[Sample #3 Explanation]

For one case $\{v_3\}=[1,0,-2]$, one optimal set of operations is as follows:

• At the first moment, node $1$ transfers $4$ energy to node $2$. After the operation, $a=[1,4,0,0,0]$, $b=1$.
• At the second moment, node $2$ transfers $2$ energy to node $4$. After the operation, $a=[1,2,0,2,0]$, $b=1$.
• At the third moment, node $2$ transfers $1$ energy to node $3$, and node $4$ transfers $1$ energy to node $5$. After the operations, $a=[1,1,1,1,1]$, $b=-1$.
• After all moments end, since there is never any node with $a_i+b<0$, all nodes are white.

[Sample #4 Explanation]

For one case $\{v_{6}\}=[1,2,1,2,1,2]$, one optimal set of operations is as follows:

• During moments $1\sim 6$, perform no operations.
• After all moments end, since there is never any node with $a_i+b<0$, all nodes are white.

[Constraints]

This problem uses bundled testdata.

Special property: the shape of the tree is guaranteed to be a "chrysanthemum" (juhua).

For $100\%$ of the testdata, $1\leq n\leq 2\times 10^5$, $1\leq k\leq 3\times 10^5$, $1\leq m\leq 50$, $1\leq t\leq 500$, and the input is guaranteed to form a tree.

[Others]

The original name of this problem was Pear Blossoms Bloom. Since the statement had errors during the contest and the original statement was not very readable, the statement was rewritten and renamed in March 2024. Renaming the title made it inconvenient for contestants to find this problem again during the contest, but the problem setter realized it only after a long time, so it was not convenient to change it back. We apologize for this.

In August 2025, the term "heat" in the statement was changed to "energy".

Translated by ChatGPT 5