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$.
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$.
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$.
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
| Subtask | Score |
|---|---|
| 1 | 11 |
| 2 | 13 |
| 3 | 31 |
| 4 | 45 |
| 5 | 0 |