P13663 「TPOI-5B」回忆

回忆。 沉溺于过去。 「死期将至」 「惟余旧忆」 回忆。

对于一棵有根树，记 $u$ 的子树中**除 $u$ 以外**的点组成的集合为 $T_u$。 定义点 $u$ 的权值 $f_u=\text{mex}_{v\in T_u}f_v$。特别地，若 $u$ 为叶子，则 $f_u=0$。 现在给定一颗树，每个点 $i$ 除了上述定义的权值外还有一个给定的权重 $a_i$。 这棵树初始只有根结点 $1$，权重为 $a_1$，有 $q$ 次操作，第 $i$ 次输入两个数 $x_i,a_{i+1}$ 代表加入一个新的结点 $i+1$，其权重为 $a_{i+1}$，它的父亲为 $x_i$，求加入这个点之后的 $\sum\limits_{j=1}^{i+1}a_jf_j$。 答案对 $10^9+7$ 取模。 注：每加入一个点后就自叶子结点向根更新 $f$ 的值。 一个集合 $M$ 的 $\operatorname{mex}(M)$ 定义为最小的没有在 $M$ 中出现的自然数。如 $\text{mex}\{1,2,3,4\}=0,\text{mex}\{0,1,3,4\}=2$。

第一行两个数 $q,a_1$，接下来接下来 $q$ 行每行两个数 $x_i,a_{i+1}$。

输出 $q$ 行，每行一个数，代表加入点 $i+1$ 后所有点的权值乘以权重的和对 $10^9+7$ 取模的结果。

### 样例 1 解释 树的形态如图：  其中各点权值依次为 $3,2,1,0,1,0,0,0$。 举例如对于 $2$ 号点，其子树内点有 $5,6,7$，权值分别为 $1,0,0$，MEX 为 $2$，所以 $2$ 的权值为 $2$。 ### 数据范围 **本题 IO 量较大，请尝试使用更快的输入输出方式。** | $\text{Subtask}$ | 子任务依赖 | $q\le $ | $x_i$ | 特殊性质 | 时间限制 | 分值 | | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | | $0$ | 无 | $5000$ | $x_i\le i$ | 保证数据随机生成 | $1\text s$ | $15$ | | $1$ | ^ | $10^5$ | $i-5\le x_i\le i$ | 无 | ^ | $5$ | | $2$ | ^ | ^ | $x_i\le2$ | ^ | ^ | ^ | | $3$ | ^ | ^ | $x_i\le i$ | 保证数据随机生成 | ^ | $15$ | | $4$ | $0,1,2,3$ | ^ | ^ | 无 | ^ | $20$ | | $5$ | $4$ | $10^6$ | ^ | ^ | ^ | $10$ | | $6$ | $5$ | $5\times10^6$ | ^ | ^ | $4\text s$ | $30$ | 对于 $100\%$ 的数据，$1\le q\le5\times10^6,1\le x_i\le i,1\le a_i\le 10^9$。