Tree

Consider a tree with $N$ vertices, numbered from $0$ to $N - 1$. Vertex $0$ is the root. Every vertex except the root has exactly one parent. For each $i$ with $1 \le i < N$, the parent of vertex $i$ is $P[i]$, where $P[i] < i$. We also set $P[0] = -1$.

For any vertex $i$ ($0 \le i < N$), the subtree of $i$ is the set containing $i$, every vertex whose parent is $i$, every vertex whose grandparent is $i$, every vertex whose great-grandparent is $i$, and so on.

The figure below shows an example tree with $N = 6$ vertices. Each arrow connects a vertex to its parent, except for the root, which has no parent. The subtree of vertex 2 contains vertices 2, 3, 4 and 5. The subtree of vertex 0 contains all 6 vertices, and the subtree of vertex 4 contains only vertex 4.

Each vertex has a nonnegative integer weight. The weight of vertex $i$ is $W[i]$.

You must answer $Q$ queries. Each query is a pair of positive integers $(L, R)$, and the answer is computed as follows.

Assign an integer coefficient to each vertex. The assignment is a sequence $C[0], \dots, C[N-1]$, where $C[i]$ is the coefficient of vertex $i$. Call this sequence a coefficient sequence. Coefficients may be negative, zero, or positive.

For a query $(L, R)$, a coefficient sequence is valid if, for every vertex $i$ ($0 \le i < N$), the sum of the coefficients over the subtree of $i$ is at least $L$ and at most $R$.

For a coefficient sequence, the cost of vertex $i$ is $|C[i]| \times W[i]$. The total cost is the sum of the costs of all vertices. For each query, output the minimum total cost over all valid coefficient sequences.

It can be shown that every query has at least one valid coefficient sequence.

• $1 \le N \le 200000$
• $1 \le Q \le 100000$
• $P[0] = -1$
• $0 \le P[i] < i$ for each $i$ with $1 \le i < N$
• $0 \le W[i] \le 1000000$ for each $i$ with $0 \le i < N$
• $1 \le L \le R \le 1000000$ in each query