题目背景

试题来源：https://koi.or.kr/archives/。中文翻译做了少量本土化修改。

按照署名—非商业性使用—相同方式共享 4.0 协议国际版进行授权。

题目描述

对于所有子节点个数为 $0$ 或 $2$ 的二叉树 $T$，定义 $S(T)$ 的值如下：

• 对于 $T$ 中某个节点 $u$，以 $u$ 为根的子树是仅包含 $u$ 和 $u$ 的所有后代节点的集合。
• $T$ 的中序遍历序列 $p(T)$ 是按照中序遍历方式访问节点所得到的序列，其定义如下：
  • 设 $r$ 为 $T$ 的根节点。记 $[r]$ 为仅包含 $r$ 的长度为 $1$ 的序列。
  • 若 $r$ 没有子节点，则 $p(T) = [r]$；
  • 若 $r$ 有两个子节点，设以 $r$ 的左子节点为根的子树为 $X$，右子节点为根的子树为 $Y$，则有 $p(T) = p(X), [r], p(Y)$，按此顺序拼接而成。
• 设 $T$ 的叶子节点数为 $k$。将编号 $1, 2, \dots, k$ 按照这些叶子节点在 $p(T)$ 中出现的顺序赋予它们。
• 若选择了一个子树，该子树中包含的所有叶子节点就被称为“被覆盖”。
• 对于 $1 \leq a \leq b \leq k$，定义 $f(a, b)$ 为为了只覆盖编号在 $[a, b]$ 区间内的叶子节点而不覆盖其他叶子节点所需选择的最少子树个数。
• $S(T)$ 的值为所有满足 $1 \leq a \leq b \leq k$ 的整数对 $(a, b)$ 的 $f(a, b)$ 之和对 $10^9 + 7$ 取模的结果。

例如，假设给定一个如图所示的二叉树 $T$，则 $f(5, 7)$ 的值为 $2$，因为可以通过选择两个子树来仅覆盖 $5$、$6$ 和 $7$ 号叶子节点。

根据上述方式，对所有 $1 \leq a \leq b \leq 7$ 的 $f(a, b)$ 求和得到 $47$，因此 $S(T) = 47 \bmod (10^9 + 7)$。

给定两个整数序列 $A_1, A_2, \dots, A_N$ 和 $B_1, B_2, \dots, B_N$，定义一系列二叉树 $T_0, T_1, \dots, T_N$ 如下：

• $T_0$ 为仅包含一个节点的树；
• 对于 $1 \leq i \leq N$，$T_i$ 是一个二叉树，其左子树为 $T_{A_i}$，右子树为 $T_{B_i}$。

请编写程序，求出 $S(T_1), S(T_2), \dots, S(T_N)$。

输入格式

第一行输入一个整数 $N$。
接下来 $N$ 行，每行输入两个整数 $A_i$ 和 $B_i$，以空格分隔。

输出格式

输出 $N$ 行，第 $i$ 行输出 $S(T_i)$ 的值。

5
0 0
1 0
1 2
3 1
4 4

3
7
21
47
254

提示

样例 1 解释

示例中的 $T_4$ 如下图所示。

约束条件

• 所有输入均为整数。
• $1 \leq N \leq 100\,000$
• $0 \leq A_i \leq i - 1\ (1 \leq i \leq N)$
• $0 \leq B_i \leq i - 1\ (1 \leq i \leq N)$

子问题

1. （5 分）$A_i = B_i = i - 1\ (1 \leq i \leq N),\ N \leq 10$
2. （10 分）$A_i = B_i = i - 1$
3. （5 分）$A_i = i - 1,\ B_i = 0$
4. （10 分）所有 $T_1, \dots, T_N$ 的节点总数不超过 $1\,000$
5. （25 分）所有 $T_1, \dots, T_N$ 的节点总数不超过 $300\,000$
6. （45 分）无额外限制条件

翻译由 ChatGPT-4o 完成