{"problem":{"name":"「FAOI-R2」霜雪千年","description":{"content":"具体来说，这棵梨树可以被抽象为一颗以 $1$ 号结点为根的树，初始时每个点都是白色。每个点有能量 $a_i$，初始时 $1$ 以外所有点的能量都为 $0$，$a_1=k$。我们设一个累计能量 $b$。 我们通过如下操作定义一个序列 $\\{v_t\\}$ 的权值： - 从小到大度过 $1,2,3,\\dots,t$ 这 $t$ 个时刻。 - 在第 $x$ 个时刻，执行 $b\\gets b+v_x$。 ","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10037"},"statements":[{"statement_type":"Markdown","content":"具体来说，这棵梨树可以被抽象为一颗以 $1$ 号结点为根的树，初始时每个点都是白色。每个点有能量 $a_i$，初始时 $1$ 以外所有点的能量都为 $0$，$a_1=k$。我们设一个累计能量 $b$。\n\n我们通过如下操作定义一个序列 $\\{v_t\\}$ 的权值：\n- 从小到大度过 $1,2,3,\\dots,t$ 这 $t$ 个时刻。\n- 在第 $x$ 个时刻，执行 $b\\gets b+v_x$。\n- 对于树上的一条边 $(u,v)$，设 $u$ 为父亲，可以选定整数 $h\\in[0,a_u]$ 执行操作 $a_u\\gets a_u-h$，$a_v\\gets a_v+h$，之后该时刻内形如 $(v,w)$ 且 $v$ 为父亲的边不能操作。\n- 若一个点 $i$ 满足 $a_i+b<0$，将 $i$ 以及 $i$ 的子树中的点染成黑色。\n- 执行最优操作以最大化第 $t$ 时刻后的白点个数，该序列权值即为最大白点个数。\n\n定义一个序列 $\\{v_t\\}$ 合法当且仅当 $\\forall i\\in[1,t]$，$\\lvert v_i\\rvert\\in[0,m]$。给定 $t$，求出所有合法序列 $\\{v_t\\}$ 的权值之和对 $998244353$ 取模后的值。\n\n## Input\n\n第一行四个非负整数 $n,m,t,k$，分别表示树的结点个数，$v_i$ 的取值范围，时刻数，初始时的 $a_1$。\n\n接下来 $n-1$ 行，每行两个正整数 $u,v$，表示 $u$ 号结点与 $v$ 号结点之间有一条边。\n\n## Output\n\n输出所有合法序列的和对 $998244353$ 取模后的结果。\n\n[samples]\n\n## Background\n\n> 在这老街回眸 烟云中追溯我是谁  \n只消暮雨点滴 便足以粉饰这是非  \n待这月色涌起 谁人轻叩这门扉  \n苔绿青石板街 斑驳了流水般岁月  \n小酌三盏两杯 理不清缠绕的情结  \n在你淡漠眉间 瞥见离人的喜悲霜雪\n\n洛天依看到了一颗雪中的梨树，梨树的根中有有限的能量，它可以向上需要传递热量到其他节点。但风雪很大，每时每刻每个节点能量都会增加会增加或减少，热量过低的节点会掉落。\n\n## Note\n\n**【样例解释】**\n\n样例 $3$ 解释：\n\n对于一种 $\\{v_3\\}=\\{1,0,-2\\}$ 的情况，一种最优操作如下：\n- 第一个时刻，$1$ 号结点传递 $4$ 能量给 $2$ 号结点，操作完毕后 $a=\\{1,4,0,0,0\\}$，$b=1$。\n- 第二个时刻，$2$ 号结点传递 $2$ 能量给 $4$ 号结点，操作完毕后 $a=\\{1,2,0,2,0\\}$，$b=1$。\n- 第三个时刻，$2$ 号结点传递 $1$ 能量给 $3$ 号结点，$4$ 号结点传递 $1$ 能量给 $5$ 号结点，操作完毕后 $a=\\{1,1,1,1,1\\}$，$b=-1$。\n- 所有时刻结束，因为始终没有 $a_i+b<0$ 的点，所以所有结点为白色。\n\n样例 $4$ 解释：\n\n对于一种 $\\{v_{6}\\}=\\{1,2,1,2,1,2\\}$ 的情况，一种最优操作如下：\n- 第 $1\\sim 6$ 个时刻，不进行操作。\n- 所有时刻结束，因为始终没有 $a_i+b<0$ 的点，所以所有结点为白色。\n\n**【数据范围】**\n\n**本题采用捆绑测试。**\n\n| Subtask 编号 | $n \\le$ | $m \\le$ | $t \\le$ | $k \\le$ | 分值 | 特殊性质 |\n| :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: |\n| $0$ | $4$ | $4$ | $4$ | $40$ | $20$ | × |\n| $1$ | $2 \\times 10^5$ | $20$ | $20$ | $1 \\times 10^5$ | $10$ | $\\checkmark$ |\n| $2$ | $2 \\times 10^5$ | $20$ | $20$ | $3 \\times 10^5$ | $20$ | × |\n| $3$ | $2 \\times 10^5$ | $50$ | $100$ | $3 \\times 10^5$ | $10$ | × |\n| $4$ | $2 \\times 10^5$ | $50$ | $500$ | $3 \\times 10^5$ | $40$ | × |\n\n特殊性质：保证树的形态是菊花。\n\n对于 $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$，保证输入构成一棵树。\n\n**【其他】**\n\n本题原名梨花开，介于赛时题面有误，且原题面可读性较低，于 2024 年 3 月重写题面并改名。改标题不便赛时选手重新找到该题，但出题人意识到时修改已久，不便改回。在此致歉。\n\n与 2025 年 8 月将题面中的“热量”改为“能量”。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10037","tags":["动态规划 DP","递推","2024","洛谷原创","O2优化","组合数学","前缀和","快速数论变换 NTT","调和级数","整除分块"],"sample_group":[["1 1 1 1","3"],["3 1 2 2\n1 2\n1 3","22"],["5 2 3 5\n1 2\n2 3\n2 4\n4 5","407"],["10 5 6 44\n1 2\n1 3\n2 5\n2 6\n3 4\n6 7\n6 8\n4 9\n9 10","10465095"]],"created_at":"2026-03-03 11:09:25"}}