← 返回题目列表

Codeforces · 1929/F

F. 萨沙和婚礼二叉搜索树

中文机器翻译题面 查看原题

克服了一切困难和磨难,萨沙终于决定和女友结婚。为此,他需要给她一枚订婚戒指。然而,他的女朋友不喜欢这种浪漫的举动,但她确实喜欢二叉搜索树$$$^{\dagger}$$$。于是萨沙决定送给她这样一棵树。

在程序员的婚礼网站上花了很多时间后,他找到了根位于顶点 $$$1$$$ 的完美二叉搜索树。在此树中,顶点 $$$v$$$ 处的值等于 $$$val_v$$$。

但过了一段时间,他忘记了一些顶点的值。为了记住找到的树,Sasha 想知道如果已知所有顶点的值都是 $$$[1, C]$$$ 段中的整数,他能在网站上找到多少个二叉搜索树。由于这个数字可能非常大,因此输出它对 $$$998\,244\,353$$$ 取模。

$$$^{\dagger}$$$二叉搜索树是一个有根二叉树,其中对于任何顶点$$$x$$$,以下属性成立:顶点$$$x$$$(如果存在)左子树中所有顶点的值都小于或等于顶点$$$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$$$ 为模。

示例

输入 #1

3
5 5
2 3 -1
-1 -1 2
4 -1 3
-1 5 -1
-1 -1 -1
3 69
2 3 47
-1 -1 13
-1 -1 69
3 3
2 3 -1
-1 -1 -1
-1 -1 -1

输出 #1

4
1
10

注意

在第一个测试用例中,二叉搜索树具有以下形式:

那么顶点处的可能值为:$$$[2, 2, 3, 2, 2]$$$、$$$[2, 2, 3, 2, 3]$$$、$$$[2, 2, 3, 3, 3]$$$ 和 $$$[3, 2, 3, 3, 3]$$$。

在第二个测试用例中,所有顶点的值都是已知的,因此只有一棵合适的二叉搜索树。