题目背景

译自 8th Romanian Master of Informatics, RMI 2020 D2T3。$\texttt{3s,0.25G}$。

题目描述

有一棵 $N$ 个节点的有根树，边有边权。节点编号为 $0\sim N-1$，$0$ 号点为根。

定义 $f(u)$ 为 $u$ 子树内经过 $u$ 的最长链的长度。

$Q$ 次操作，一次操作将一条边的边权加上一个正数。在第一次操作前，和每次操作后，求出 $\displaystyle \left(\sum_{1\le i\le N} f(i)\right)\bmod (10^9+7)$。

输入格式

第一行，一个正整数 $N$。

第二行，$(N-1)$ 个整数 $p_1,\cdots,p_{N-1}$，$p_i$ 表示 $i$ 号点的父亲为 $p_i$。

第三行，$(N-1)$ 个正整数 $d_1,\cdots,d_{N-1}$，$d_i$ 表示 $(i,p_i)$ 边边权为 $d_i$。

第四行，一个正整数 $Q$。

接下来 $Q$ 行，每行两个正整数 $x,v$，表示给 $(x,p_x)$ 边权增加 $v$。

输出格式

输出 $(Q+1)$ 行，每行一个整数：

• 第一行，输出第一次操作前的答案。
• 接下来 $Q$ 行，输出每次操作后的答案。

5
0 0 1 1
0 0 0 0
10
1 2
2 2
3 2
4 2
4 1
3 1
2 1
1 1
4 1000
2 1000

0
2
4
8
10
12
13
14
15
2015
3015

提示

对于 $100\%$ 的数据，保证：

• $1\le N,Q\le 10^5$；
• $1\le d_i\le 10^9$；
• $0\le p_i\lt i$；
• $1\le v\le 10^9$；
• $1\le x\lt N$。

• 特殊性质 A：树高不大于 $50$；
• 特殊性质 B：$d_i=10^9$，$v=1$。