Minimizing Weighted Coefficient Cost on a Tree

You are given a rooted tree with N nodes numbered from 0 to N-1. Node 0 is the root, and for every node i with 1 ≤ i < N its unique parent is P[i] (with P[i] < i). We set P[0] = -1 by convention.

Each node i is assigned a nonnegative integer weight W[i]. For any node i (0 ≤ i < N), its subtree is defined as the set that includes:

• Node i itself,
• All nodes whose parent is i,
• All nodes whose parent's parent is i,
• And so on.

For a given assignment of coefficients (an integer sequence C[0], C[1], ..., C[N-1], where each C[i] may be negative, zero, or positive), we define the subtree sum at node i as:

$$S[i] = C[i] + \sum_{\text{child } j \text{ of } i} S[j] $$

For every node i the assigned coefficient sequence is called valid with respect to a query (L,R) (where both L and R are positive integers) if:

$$L \le S[i] \le R \quad \text{for all } 0 \le i < N. $$

The cost at node i is defined as:

$$cost(i) = |C[i]| \times W[i].$$

The overall cost of an assignment is the sum of costs for all nodes. Your task is to answer Q queries. In each query you are given two integers L and R and you must compute the minimum overall cost that can be achieved by some valid coefficient sequence.

You are guaranteed that for every query, there exists at least one valid coefficient sequence.

---

Implementation Details

You need to implement the following two functions:

void init(vector P, vector W)

• P and W are two arrays of length N that record the parent and weight of each node respectively. This function will be called exactly once per test case at the beginning.

long long query(int L, int R)

• L and R are two positive integers that describe a query.
• This function will be called exactly Q times (after init has been called) for each test case.
• Your function should return the minimum overall cost for that query.

Note on the Approach: One way to solve this problem is to observe that if we define S[i] as the subtree sum at node i (which must lie in \([L,R]\)) and note that C[i] = S[i] - \sum_{\text{child } j} S[j], then the overall cost is:

$$\text{Total Cost} = \sum_{i=0}^{N-1} |S[i] - \sum_{j \in child(i)} S[j]| \times W[i]. $$

The task reduces to choosing a valid S assignment for every node. A recursive dynamic programming approach (via DFS and combining results from children) can be used. For a leaf node, you choose S[i] in \([L,R]\) at a cost of S[i] \times W[i], and for an internal node you combine the possibilities from its children. In the solutions provided below, a DFS routines performs such a DP where for each node we keep a mapping from possible S values to the minimum cost for the subtree rooted at that node.

inputFormat

The input begins with an integer N denoting the number of nodes. The next line contains N integers representing array P (with P[0] = -1), followed by a line with N integers representing the weight array W. The next line contains an integer Q representing the number of queries. Each of the following Q lines contains two positive integers L and R.

outputFormat

For each query, output a line with a single integer: the minimum overall cost achievable using some valid coefficient sequence.

sample

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

7
8

</p>