Dynamic Diameter 2

Description

You are given an edge-weighted tree of size $N$ where vertices are numbered from $0$ to $N-1$. The tree is rooted at vertex $0$. Vertex $i$ is connected to vertex $p_i$ with an edge of length $d_i$.

For each vertex $i$, let $l_i$ denote the length of the longest path such that vertex $\mathbf{i}$ is contained in the path and all vertices used are contained in the subtree of $i$. Recall a path is a sequence of vertices $a_1,a_2,\ldots,a_k$ such that all $a$ are distinct and $a_i$ and $a_{i+1}$ is connected by an edge. Your job is to find $\sum_{i=1}^n l_i$.

Since this problem is not hard enough to be a December Course problem 5, we are going to make $Q$ modifications to the tree. In the $i$-th modification you will be given $v_i$ and $add_i$. You should increase the edge connecting vertex $v_i$ and $p_{v_i}$ by $add_i$. Note that updates are persistent, modifications made to the tree will apply when processing futures modifications.

Also because $\sum_{i=1}^n l_i$ is very big, you should find the answer modulo $10^9+7$.

Input

The first line contains a single integer $N$, the number of vertices in the tree.

The second line contains $N-1$ integers $p_1,p_2,\ldots,p_{N-1}$.

The third line contains $N-1$ integers $d_1,d_2,\ldots,d_{N-1}$.

The fourth line contains $Q$, the number of updates.

The following $Q$ lines contains two integers $v_i$ and $add_i$.

Output

You should output $Q+1$ lines. The first line should contain the answer before any updates are made. On the $i+1^\text{th}$ line you should print the answer after the $i^\text{th}$ modification.

All answers must be printed modulo $10^9+7$.

Constraints

  • $2 \leq N \leq 100~000$
  • $1 \leq Q \leq 100~000$
  • $1 \leq d_i \leq 100~000~000$
  • $0 \leq p_i < i$
  • $1 \leq v_i < N$
  • $1 \leq add_i \leq 1~000~000~000$

Subtasks

  • $1 \leq N \leq 1~000$, $1 \leq Q \leq 1~000$ ($11$ points)
  • The height of the tree is at most $50$ ($13$ points)
  • $d_i = 100~000~000$, $add_i=1$ ($31$ points)
  • No additional constraints ($45$ points)

Sample Input

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

Sample Output

0
2
4
8
10
12
13
14
15
2015
3015

Submitting to 'Dynamic Diameter 2'


You're not logged in! Click here to login


Submitting to 'Dynamic Diameter 2'


You're not logged in! Click here to login


Submitting .cpp to 'Dynamic Diameter 2'


You're not logged in! Click here to login

Time Limit: 5 Seconds
Memory Limit: 1024MB
No. of ACs: 1
Your best score: 0
Source: RMI 2020
Editorial: 1

Subtask Score
1 11
2 13
3 31
4 45
5 0