Problem Description

Given a rooted tree with $n$ nodes, the weight of node $i$ is $a_i$.

This tree supports the following type of query:

• Given a node $u$ and a parameter $x$, suppose the weights of all nodes are increased by $x$. Under this assumption, find: among all connected sets of nodes that are completely inside the subtree of $u$ and that contain $u$, what is the maximum possible sum of weights?

Input Format

The first line contains two positive integers $n$ and $m$.

The second line contains $n-1$ positive integers $f_2,f_3,\dots,f_n$, which are the parent node indices of nodes $2,3,\dots,n$ respectively, and it is guaranteed that $1\le f_i<i$.

The third line contains $n$ integers $a_1,a_2,\dots,a_n$, which are the node weights of nodes $1,2,\dots,n$ respectively.

The next $m$ lines each contain a positive integer $u$ and an integer $x$, representing one query. It is guaranteed that $1\le u\le n$.

Output Format

Output $m$ lines, each containing one integer, which is the answer to the corresponding query.

10 6
1 1 2 2 3 5 5 5 6
5 2 3 1 -5 -7 1 1 1 2
1 0
1 -2
1 3
2 1
5 0
5 -2

11
4
34
7
-2
-7

Hint

Constraints

This problem uses bundled testdata.

• Subtask 1 (5 pts): $n,m\le 1000$.
• Subtask 2 (10 pts): $n,m\le 10^5$ and $|a_i|,|x|\le 50$.
• Subtask 3 (15 pts): $n\le 1000$.
• Subtask 4 (47 pts): $n,m\le 10^5$.
• Subtask 5 (23 pts): no special restrictions.

For all testdata, $1\le n,m\le 10^6$, $|a_i|,|x|\le 10^8$, and it is guaranteed that $1\le u\le n$.

Translated by ChatGPT 5