Problem Description

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

This tree supports one type of query:

• Given a node $u$ and a parameter $x$, suppose the weights of all nodes are increased by $x$. In this situation, find: among all connected vertex sets that are completely inside the subtree of $u$ and 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. 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 weights of nodes $1,2,\dots,n$, respectively.

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

Output Format

Output $m$ lines, each containing one integer, 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

Idea: w33z8kqrqk8zzzx33, Solution: w33z8kqrqk8zzzx33&ccz181078, Code: w33z8kqrqk8zzzx33, Data: w33z8kqrqk8zzzx33

For $100\%$ of the 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