题目描述

题目译自 Romanian Master of Informatics 2020 Day2 T3 「Arboras」

魔法师 Roxanne 在研究古老的魔法之后，决定去当地的咖啡馆放松一下。她在咖啡馆里看到了一棵奇怪的树状结构，称为 arboras。这棵树由 $N$ 个编号为 $0$ 到 $N-1$ 的节点组成，其中节点 $0$ 是根节点，其他节点都有一个唯一的父节点。

Roxanne 对这棵树很感兴趣，她决定将一些魔法咖啡倒入其中一个节点。如果将咖啡倒入节点 $u$，那么咖啡就会向下流动，经过以节点 $u$ 为根的子树。由于这是魔法咖啡，它不会随机流动：它会占据子树中尽可能长的链，同时经过节点 $u$。倒入咖啡时损失的咖啡量与咖啡占据的链的长度成正比。Roxanne 将这个量表示为 $r_u$。请注意，树中的各个边可能具有不同的长度。

Roxanne 对如果她将咖啡倒入树中的所有节点，她将损失多少咖啡量感兴趣，即树中所有节点 $u$ 的 $r_u$ 之和。这最初并不难计算，但随后程序员决定挑战她，并增加某些边的长度 $Q$ 次。你能帮助 Roxanne 找到咖啡在倒入所有节点时占据的所有链的总长度，包括初始状态和 $Q$ 次更新后的状态吗？请注意，答案需要对 $10^9+7$ 取模。

输入格式

第一行包含整数 $N$，表示节点的数量。

第二行包含 $N-1$ 个整数 $p_1, p_2, \ldots , p_{N-1}$，其中 $p_v$ 是节点 $v$ 的父节点，而节点 $0$ 是根节点。

第三行包含 $N-1$ 个整数 $d_1, d_2, \ldots , d_{N-1}$，其中 $d_v$ 是节点 $v$ 和 $p_v$ 之间的边的长度。

第四行包含 $Q$，表示更新的数量。

接下来的 $Q$ 行，每行包含两个整数 $v_i$ 和 $add_i$，表示第 $i$ 次更新：节点 $v_i$ 和 $p_v$ 之间的边的长度增加了 $add_i$。

输出格式

输出 $Q+1$ 行，第 $i+1$ 行应该输出第 $i$ 次更新后的答案。第一行应该输出任何更新之前的答案。

所有答案必须对 $10^9+7$ 取模。

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
2

数据范围与提示

对于所有输入数据，满足：

• $1 \leq N \leq 10^5$
• $1 \leq Q \leq 10^5$
• 对于所有 $1 \leq i \leq N-1$，$1 \leq d_{i} \leq 10^8$
• $0 \leq p_{i}<i$
• 对于所有 $1 \leq i \leq Q$，$1 \leq add_{i} \leq 10^{9}$

详细子任务附加限制及分值如下表所示。