P17316 [KismetOI 2026 I] 孤独绽放的彼岸花


沙耶正在散心。 这片小巷可以视作一棵 $n$ 个节点的树，节点从 $1$ 至 $n$ 编号，沙耶当前在节点 $1$。 树上的一条边就是一条小道，边权代表着走过这条小道耗费的体力，保证边权为非负整数。 沙耶想走过 $k$ 条小道。她不会再走已经走过的路，同时她也不会在这片小巷消耗大于 $S$ 的体力。 沙耶询问过路人这片小巷的情况，得知了树的形态，并且还得知至多耗费 $X$ 的体力就可以从点 $1$ 走到任何一处。可惜过路人忘记了每条小道的具体边权。 沙耶好奇，如果所有合法局面等概率随机出现，在当前局面存在一种方案使得她可以走过至少 $k$ 条小道的概率有多大？一个局面合法当且仅当该局面下所有边权均为非负整数且从点 $1$ 到任意一点的距离不超过 $X$，两个局面不同当且仅当存在一条边边权在两种情况下不同。 沙耶希望你告诉她这个概率对 $998244353$ 取模后的值。 额外地，保证答案在模 $998244353$ 下有意义。

首先输入一行一个整数 $T$ 表示数据组数。对于每组数据，输入格式如下： 第一行输入四个整数 $n,k,S,X$。 第二行输入 $n-1$ 个整数，第 $i$ 个数表示节点 $i+1$ 的父节点编号。点 $1$ 为根节点。

对每组数据输出一行一个整数表示答案。

### 样例解释 给定树的形态如下图所示：  容易证明有 $10$ 种合法局面，其中 $6$ 种符合条件的局面如下图所示：  上述 $6$ 种局面均满足存在一条从 $1$ 走到 $4$ 或 $5$ 的边权和为 $0$ 的路径，符合题意。 故概率为 $\frac{3}{5}$，对 $998244353$ 取模后得到 $798595483$。 ### 数据范围 对所有数据，满足 $1\le T\le 8$。$1\le n,k\le 3000$，$0\le S,X\le 10^{18}$。 ::cute-table{tuack} |子任务编号|$n\le$|性质 A|性质 B|性质 C|分值| |:-:|:-:|:-:|:-:|:-:|:-:| |#1|$5$|否|否|否|$5$| |#2|^|是|^|^|$5$| |#3|$100$|^|^|^|$5$| |#4|^|否|是|^|$10$| |#5|^|^|否|是|$10$| |#6|^|^|^|否|$15$| |#7|$3000$|是|^|^|$5$| |#8|^|否|是|^|$10$| |#9|^|^|否|是|$10$| |#10|^|^|^|否|$25$| 性质 A：$X\le 3000$。 性质 B：$X-S\le 3000$。 性质 C：保证树为一条链。