Background

When submitting, please do not include tree.h.

Please do not submit using C++14 (GCC 9).

Problem Description

There is a tree with $N$ nodes, numbered from $0$ to $N-1$. Node $0$ is the root of the tree. Every node except the root has a unique parent. For each $i$ with $1 \leq i < N$, the parent of node $i$ is $P[i]$, where $P[i] < i$. We define $P[0] = -1$.

For each node $i$ ($0 \leq i < N$), the subtree of $i$ is the set of nodes consisting of:

• $i$, and
• all nodes whose parent is $i$, and
• all nodes whose parent’s parent is $i$, and
• all nodes whose parent’s parent’s parent is $i$, and
• and so on.

The figure below shows an example of a tree with $N = 6$ nodes. Each arrow goes from a node to its parent (except for the root node, since it has no parent). The subtree of node $2$ contains nodes $2, 3, 4$, and $5$. The subtree of node $0$ contains all $6$ nodes of the tree, while the subtree of node $4$ contains only node $4$ itself.

Each node is assigned a non-negative integer weight. The weight of node $i$ ($0 \leq i < N$) is denoted by $W[i]$.

Your task is to write a program to answer $Q$ queries, where each query is represented by a pair of positive integers $(L, R)$. The answer to each query should be computed as follows.

For every node in the tree, assign an integer called a coefficient. Such an assignment is described by a sequence $C[0], \ldots, C[N-1]$, where $C[i]$ ($0 \leq i < N$) is the coefficient assigned to node $i$. We call this sequence a coefficient sequence. Note that the elements of a coefficient sequence can be negative, $0$, or positive.

For a query $(L, R)$, a coefficient sequence is called valid if for every node $i$ ($0 \leq i < N$), the following condition holds: the sum of coefficients in the subtree of node $i$ is at least $L$ and at most $R$.

Given a coefficient sequence $C[0], \ldots, C[N-1]$, the cost of node $i$ is $|C[i]| \cdot W[i]$, where $|C[i]|$ is the absolute value of $C[i]$. The total cost is the sum of the costs of all nodes. For each query, your task is to compute the minimum total cost that can be achieved by some valid coefficient sequence.

It can be proven that for every query, there exists at least one valid coefficient sequence.

Implementation Details

You need to implement the following two functions:

void init(std::vector<int> P, std::vector<int> W)

• $P$, $W$: two integer arrays of length $N$, recording the parent and weight of each node.
• For each test case, this function will be called exactly once when the grader starts interacting with your program.

long long query(int L, int R)

• $L$, $R$: two integers describing one query.
• For each test case, after init is called, this function will be called $Q$ times.
• This function should return the answer for the given query.

Input Format

The sample grader reads input in the following format:

N
P[1]  P[2] ...  P[N-1]
W[0]  W[1] ...  W[N-2] W[N-1]
Q
L[0]  R[0]
L[1]  R[1]
...
L[Q-1]  R[Q-1]

Here, $L[j]$ and $R[j]$ ($0 \leq j < Q$) are the input parameters for the $j$-th call to query. Note that the second line of the input contains only $N-1$ integers, because the sample grader does not read the value of $P[0]$.

Output Format

The sample grader prints your answers in the following format:

A[0]
A[1]
...
A[Q-1]

Here, $A[j]$ ($0 \leq j < Q$) is the value returned by the $j$-th call to query.

3
0 0
1 1 1
2
1 1
1 2

3
2

Hint

Consider the following call:

init([-1, 0, 0], [1, 1, 1])

This tree has $3$ nodes: the root node and its $2$ child nodes. All nodes have weight $1$.

query(1, 1)

In this query, $L = R = 1$, which means the sum of coefficients in every subtree must be equal to $1$. Consider the coefficient sequence $[-1, 1, 1]$. The tree and the corresponding coefficients (in the shaded rectangles) are shown below.

For each node $i$ ($0 \leq i < 3$), the sum of coefficients over all nodes in the subtree of $i$ is $1$. Therefore, the coefficient sequence is valid. The total cost is computed as follows:

Therefore, the total cost is $3$. This is the only valid coefficient sequence, so the call should return $3$.

query(1, 2)

For this query, the minimum total cost is $2$, which can be achieved with the coefficient sequence $[0, 1, 1]$.

Constraints

• $1 \leq N \leq 200\,000$
• $1 \leq Q \leq 100\,000$
• $P[0] = -1$
• For all $i$ with $1 \leq i < N$, $0 \leq P[i] < i$
• For all $i$ with $0 \leq i < N$, $0 \leq W[i] \leq 1\,000\,000$
• In each query, $1 \leq L \leq R \leq 1\,000\,000$

Translated by ChatGPT 5