Maximum Subtree Sum in Modified Tree

Given a rooted tree with n nodes. Each node i has an integer weight a_i. The tree is rooted at node 1. For each query, you are given a node u and an integer parameter x. First, assume that every node's weight is increased by x (i.e. each node now has weight a_i + x). Under this modification, consider all connected subsets of nodes that:

• are completely contained in the subtree rooted at u, and
• contain the node u

Your task is to determine the maximum possible sum of weights for such a connected subset.

The answer for a query on node u and parameter x can be computed with a DFS using the recurrence:

\(f(u) = (a_u + x) + \sum_{v \in children(u)} \max(0, f(v))\)

where the summation goes over all children of u in the tree. The value f(u) is the maximum achievable sum for a connected subset of the subtree of u that includes u.

inputFormat

The first line contains two integers n and q (1 ≤ n, q ≤ 10⁵), representing the number of nodes in the tree and the number of queries.

The second line contains n integers: a₁, a₂, ... , a_n, where a_i is the weight of node i.

The next n-1 lines describe the tree structure. For each i from 2 to n, the (i+1)-th line contains a single integer p_i (1 ≤ p_i ≤ n) which denotes the parent of node i. It is guaranteed that the tree is rooted at node 1.

Each of the following q lines contains two integers u and x (1 ≤ u ≤ n, -10⁹ ≤ x ≤ 10⁹), representing a query.

outputFormat

For each query, output a single integer — the maximum sum of weights for a connected subset that is completely contained in the subtree of the given node u and contains u, after increasing every node’s weight by x.

sample

5 3
1 2 3 4 5
1
1
2
3
1 0
2 1
3 -2

15
8
4