Myth is hungry. Luckily, he just found a cereal tree!
The cereal tree can be represented by a tree rooted at node $$$1$$$ with $$$n$$$ nodes numbered $$$1 \dots n$$$ and $$$n-1$$$ edges. Each node has some cereal with with a deliciousness of $$$v_i$$$, which could be positive or negative.
Myth wants to eat some connected component of the tree. The enjoyment derived from eating a connected component of the tree is the sum of $$$v_i$$$ for all nodes $$$i$$$ in the connected component.
There are $$$q$$$ queries made to the tree in the form of $$$x$$$ $$$c$$$:
Some sugar is sprinkled on node $$$x$$$, which increases the deliciousness $$$v_x$$$ by $$$c$$$. Mythreya then wants to know the maximum enjoyment he can derive from eating a component, such that the highest node in the component (the node closest to the root) is $$$x$$$.
The first line contains two space separated integers: $$$n$$$ and $$$q$$$ ($$$1 \leq n, q \leq 5 \cdot 10^5$$$)
The next line contains $$$n$$$ space separated integers, with the $$$i$$$-th integer representing $$$v_i$$$ ($$$-10^9 \leq v_i \leq 10^9$$$)
The next line contains $$$n-1$$$ space separated integers $$$p_2 \dots p_n$$$, indicating that the parent of node $$$i$$$ is $$$p_i$$$ ($$$1 \leq p_i \leq i-1$$$).
The next $$$q$$$ lines contain two integers: $$$x$$$ and $$$c$$$, indicating a query. ($$$1 \leq x \leq n, 0 \leq c \leq 10^9$$$)
For each query $$$x$$$ $$$c$$$, output the maximum enjoyment of any component, given that the component's closest node to the root is $$$x$$$.
3 3-1 -1 -11 22 21 03 0
1 0 -1
Note: $$$O(n \log^2 (n))$$$ solutions are not intended to pass given constraints.
