「FAOI-R2」梨花开 (C)

题目背景

> 忽如一夜春风来,千树万树梨花开。 雪,覆盖了大漠上的一颗颗树,仿佛朵朵梨花盛开。但是令 krjt 意想不到的是,这些树居然真的是梨树!

题目描述

krjt 的目光注视在一棵以 $1$ 号结点为根的,$n$ 个结点的梨树上。 这颗梨树的每个点在每一刻都可以做**任意次**以下操作:将自己的**基本**热量提供**任意正整数量**给某个儿子。 **但需要注意的是,在同一个时刻里,只有当一个结点的所有儿子结束操作后,该结点才能操作。** 雪纷纷地下着,梨树在 $t$ 个时刻的冬天里,第 $i$ 天**所有操作完成后**每个结点的都会加上 $v_i$ 点**附加**热量,若**加上后**该结点的**总**热量仍然 $<0$ 则会连同它的子树一起冻死(自动与其祖先断开,掉到地上)。每个 $v_i$ 都是 $[-m,m]$ 中的一个不确定的整数值。 梨树定义一个序列 $\{v_t\}$ 的价值为它作为每时刻增加的热量时,梨树最多保留的结点数。 梨树不愿在这个冬天死去,希望求出所有方案的价值和,以保留尽量多的结点迎接春天,绽放花朵。因为在冬天前,它的根结点储蓄了 $k$ 点**基本**热量(和 $0$ 点附加热量,其他结点储蓄了 $0$ 点热量),这是自知活不过冬天的伙伴给它的。 而它伙伴在最后一点意识隐隐消失时,仿佛能够看到:一夜春风轻抚,冰雪消融,树林里朵朵梨花开…… 答案对 $998244353$ 取模。

输入输出格式

输入格式


第一行四个非负整数 $n,m,t,k$,分别表示树的结点个数,$v_i$ 的取值范围,冬天的时长,根结点原本存储的热量。 接下来 $n-1$ 行,每行两个正整数 $u,v$,表示 $u$ 号结点与 $v$ 号结点之间有一条边。

输出格式


输出所有 $(2m+1)^{t}$ 种情况的答案的**和对 $998244353$ 取模**后的结果。

输入输出样例

输入样例 #1

1 1 1 1

输出样例 #1

3

输入样例 #2

3 1 2 2
1 2
1 3

输出样例 #2

22

输入样例 #3

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

输出样例 #3

407

输入样例 #4

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

输出样例 #4

10465095

说明

样例 $3$ 解释: 对于一种 $\{v_3\}=\{1,0,-2\}$ 的情况,一种最优操作如下: - 第一个时刻,$1$ 号结点传递 $4$ 热量给 $2$ 号结点,操作完毕并增加 $v_1=1$ 后每个结点的热量分别为 $2,5,1,1,1$。 - 第二个时刻,$2$ 号结点传递 $2$ 热量给 $4$ 号结点,操作完毕并增加 $v_2=0$ 后每个结点的热量分别为 $2,3,1,3,1$。 - 第三个时刻,$2$ 号结点传递 $1$ 热量给 $3$ 号结点,$4$ 号结点传递 $1$ 热量给 $5$ 号结点,操作完毕并增加 $v_3=-2$ 后每个结点的热量分别为 $0,0,0,0,0$。 - 第四个时刻,冬天过去,$5$ 个结点全部存活。 样例 $4$ 解释: 对于一种 $\{v_{6}\}=\{1,2,1,2,1,2\}$ 的情况,一种最优操作如下: - 每个时刻都不进行操作。 - 第 $7$ 个时刻,冬天过去,$5$ 个结点全部存活。 ------------ **本题采用捆绑测试。** | Subtask 编号 | $n \le$ | $m \le$ | $t \le$ | $k \le$ | 分值 | | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | | $0$ | $4$ | $4$ | $4$ | $40$ | $20$ | | $\color{red}1$ | $\color{red}2 \times 10^5$ | $\color{red}20$ | $\color{red}20$ | $\color{red}1 \times 10^5$ | $\color{red}10$ | | $2$ | $2 \times 10^5$ | $20$ | $20$ | $3 \times 10^5$ | $20$ | | $3$ | $2 \times 10^5$ | $50$ | $100$ | $3 \times 10^5$ | $10$ | | $4$ | $2 \times 10^5$ | $50$ | $500$ | $3 \times 10^5$ | $40$ | **特殊性质:对于 Subtask 1,保证树的形态是菊花。** 对于 $100\%$ 的数据,$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$,保证输入构成一棵树。