409404: GYM103500 C eerT tuC kniL

You are given a tree with $$$n$$$ nodes, labeled $$$1\dots n$$$ and rooted at $$$1$$$. The weight of the $$$i$$$-th node is an integer $$$a_i$$$.

There are $$$m$$$ scenarios, denoted by a node $$$u$$$ and an integer $$$x$$$. For each scenario, suppose we increase the weight of all nodes in the subtree of $$$u$$$ by $$$x$$$; over all connected induced subgraphs of the subtree of $$$u$$$ containing $$$u$$$, what is maximum possible sum of node weights of such a subgraph?

The first line contains two integers $$$n$$$ and $$$m$$$, the number of nodes and the number of scenarios, respectively ($$$1\le n,m\le 10^6$$$).

The second line contains $$$n-1$$$ integers $$$f_2,f_3,\dots,f_n$$$, where $$$f_i$$$ is the father of node $$$i$$$ ($$$1\le f_i<i$$$).

The third line contains $$$n$$$ integers $$$a_1,a_2,\dots,a_n$$$ ($$$|a_i|\le 10^8$$$).

The $$$i$$$-th of the following $$$m$$$ lines contain two integers $$$u$$$ and $$$x$$$ ($$$1\le u\le n$$$, $$$|x|\le 10^8$$$) corresponding to one scenario.

For each scenario, output one line, corresponding to the maximum possible sum of node weights of the described subgraph in this scenario.

• In the first subtask, worth $$$5$$$ points, $$$n,m\le 1000$$$.
• In the second subtask, worth $$$10$$$ points, $$$n,m\le 10^5$$$ and $$$|a_i|,|x|<50$$$.
• In the third subtask, worth $$$15$$$ points, $$$n\le 1000$$$.
• In the fourth subtask, worth $$$47$$$ points, $$$n,m\le 10^5$$$.
• In the final subtask, worth $$$23$$$ points, no additional constraints are posed.

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