#213394. [NOI2025] 数字树

给定一棵 个结点的二叉树，其中每个非叶结点都有 恰好 两个子结点。非叶结点编号为 到 ，叶子结点编号为 到 。初始时，每个叶子结点上都没有数字。

定义一个 DFS 序是 优美的，当且仅当按该 DFS 序将 所有标有数字的叶子结点 上的数字拼成一个序列时，该序列可以通过若干次 消除相邻相同数字 的方式得到空序列。例如，在下图中，若叶子结点 上标有数字 ，叶子结点 上标有数字 ，则按 DFS 序 将所有标有数字的叶子结点上的数字拼成的序列为 ，可以通过消除相邻的 的方式得到 ，再通过消除相邻的 的方式得到空序列，因此该 DFS 序是优美的；而按 DFS 序 将所有标有数字的叶子结点上的数字拼成的序列为 ，无法通过若干次消除相邻相同数字的方式得到空序列，因此该 DFS 序不是优美的。

给定 次操作，第 () 次操作会选择两个 没有数字 的叶子结点，然后将这两个结点标上数字 。保证在每次操作后，存在至少一个优美的 DFS 序。你需要求出每次操作后的优美的 DFS 序的数量。由于答案可能较大，你只需要求出答案对 取模后的结果。

输入的第一行包含一个非负整数 ，表示测试点编号。 表示该测试点为样例。

输入的第二行包含一个正整数 ，表示二叉树的结点个数为 。

输入的第 () 行包含两个正整数 和 ，分别表示结点 的左右子结点。保证 ，且所有的 互不相同。

输入的第 () 行包含两个正整数 ，表示第 次操作选择的叶子结点的编号。保证 ，且所有的 互不相同。

输出 行，其中第 () 行包含一个非负整数，表示第 次操作后的优美的 DFS 序的数量对 取模后的结果。

样例输入 1

0
2
4 2
3 7
5 6
4 6
5 7

样例输出 1

8
4

样例输入 2

0
6
2 3
4 21
22 23
5 11
6 8
7 9
12 13
10 18
14 15
16 17
19 20
12 13
14 15
16 19
17 18
20 21
22 23

样例输出 2

2048
2048
2048
1024
512
512

样例 1 解释

该样例即【题目描述】中所示的例子。

• 第一次操作后，叶子结点 和 上标有数字 ，叶子结点 和 上没有数字，因此按任意 DFS 序拼成的序列均为 ，即所有的 个 DFS 序都是优美的。
• 第二次操作后，叶子结点 上分别标有数字 ，因此共有 个优美的 DFS 序，分别为 。

样例 3

见选手目录下的 tree/tree3.in 与 tree/tree3.ans。

该样例满足测试点 的约束条件。

样例 4

见选手目录下的 tree/tree4.in 与 tree/tree4.ans。

该样例满足测试点 的约束条件。

样例 5

见选手目录下的 tree/tree5.in 与 tree/tree5.ans。

该样例满足测试点 的约束条件。

样例 6

见选手目录下的 tree/tree6.in 与 tree/tree6.ans。

该样例满足测试点 的约束条件。

数据范围

对于所有测试数据，保证：

• ；
• 对于所有 ，均有 ，且所有的 互不相同；
• 对于所有 ，均有 ，且所有的 互不相同；
• 在每次操作后，存在至少一个优美的 DFS 序。

::cute-table{tuack}

特殊性质 A：保证每次操作选择的两个叶子结点位于结点 1 的不同子树内。

特殊性质 B：保证存在非负整数 满足 ，且对于所有 ，均有 。

附加文件来自于 QOJ。