CF1929F Sasha and the Wedding Binary Search Tree

经历了重重困难，Sasha 终于决定和他的女朋友结婚。为此，他需要送她一枚订婚戒指。然而，他的女朋友并不喜欢这种浪漫的举动，但她喜欢二叉搜索树 $ ^{\dagger} $。于是 Sasha 决定送她这样一棵树。 在程序员婚礼网站上花了很长时间后，他找到了一个以 $1$ 号结点为根的完美二叉搜索树。在这棵树中，第 $v$ 个结点上的值为 $val_v$。 但过了一段时间，他忘记了部分结点上的值。在试图回忆起这棵树时，Sasha 想知道——如果已知所有结点上的值都是区间 $[1, C]$ 内的整数，那么他在网站上可能找到多少种二叉搜索树。由于这个数可能非常大，请输出其对 $998\,244\,353$ 取模的结果。 $ ^{\dagger} $ 二叉搜索树是一种有根二叉树，对于任意结点 $x$，都满足如下性质：$x$ 的左子树（如果存在）上的所有结点的值都小于等于 $x$ 结点的值，右子树（如果存在）上的所有结点的值都大于等于 $x$ 结点的值。

每组测试数据包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^5$），表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含两个整数 $n$ 和 $C$（$2 \leq n \leq 5 \cdot 10^5$，$1 \leq C \leq 10^9$），分别表示树的结点数和结点允许的最大值。 接下来的 $n$ 行描述树的结点。第 $i$ 行包含三个整数 $L_i, R_i$ 和 $val_i$（$-1 \le L_i, R_i \le n$，$-1 \le val_i \le C$，$L_i, R_i, val_i \ne 0$），分别表示第 $i$ 个结点的左儿子编号、右儿子编号和该结点的值。如果 $L_i = -1$，则第 $i$ 个结点没有左儿子；如果 $R_i = -1$，则第 $i$ 个结点没有右儿子；如果 $val_i = -1$，则第 $i$ 个结点的值未知。 保证至少存在一种合法的二叉搜索树。 保证所有测试用例中 $n$ 的总和不超过 $5 \cdot 10^5$。

对于每个测试用例，输出一个整数，表示满足条件的二叉搜索树的数量，对 $998\,244\,353$ 取模。

在第一个测试用例中，二叉搜索树的结构如下：  那么结点可能的取值为：$[2, 2, 3, 2, 2]$，$[2, 2, 3, 2, 3]$，$[2, 2, 3, 3, 3]$，以及 $[3, 2, 3, 3, 3]$。 在第二个测试用例中，所有结点的值都已知，因此只有一种合法的二叉搜索树。 由 ChatGPT 4.1 翻译