32264번 - Tree 서브태스크다국어언어 제한함수 구현

문제

Consider a tree consisting of $N$ vertices, numbered from 0ドル$ to $N - 1$. Vertex 0ドル$ is called the root. Every vertex, except for the root, has a single parent. For every $i,ドル such that 1ドル ≤ i < N,ドル the parent of vertex $i$ is vertex $P[i],ドル where $P[i] < i$. We also assume $P[0] = -1$.

For any vertex $i$ (0ドル ≤ i < N$), the subtree of $i$ is the set of the following vertices:

• $i,ドル
• and any vertex whose parent is $i,ドル
• and any vertex whose parent's parent is $i,ドル
• and any vertex whose parent's parent's parent is $i,ドル and etc.

The picture below shows an example tree consisting of $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 of the tree and the subtree of vertex 4ドル$ contains only vertex 4ドル$.

Each vertex is assigned a nonnegative integer weight. We denote the weight of vertex $i$ (0ドル ≤ i < N$) by $W[i]$.

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

Consider assigning an integer, called a coefficient, to each vertex of the tree. Such an assignment is described by a sequence $C[0],\dots ,C[N - 1],ドル where $C[i]$ (0ドル ≤ i < N$) is the coefficient assigned to vertex $i$. Let us call this sequence a coefficient sequence. Note that the elements of the coefficient sequence can be negative, 0ドル,ドル or positive.

For a query $(L,R),ドル a coefficient sequence is called valid if, for every vertex $i$ (0ドル ≤ i < N$), the following condition holds: the sum of the coefficients of the vertices in the subtree of vertex $i$ is not less than $L$ and not greater than $R$.

For a given coefficient sequence $C[0],\dots ,C[N - 1],ドル the cost of a vertex $i$ is $|C[i]| \cdot W[i],ドル where $|C[i]|$ denotes the absolute value of $C[i]$. Finally, the total cost is the sum of the costs of all vertices. Your task is to compute, for each query, the minimum total cost that can be attained by some valid coefficient sequence.

It can be shown that for any query, at least one valid coefficient sequence exists.

구현 상세

You should implement the following two procedures:

void init(std::vector P, std::vector W)

• $P,ドル $W$: arrays of integers of length $N$ specifying the parents and the weights.
• This procedure is called exactly once in the beginning of the interaction between the grader and your program in each test case.

long long query(int L, int R)

• $L,ドル $R$: integers describing a query.
• This procedure is called $Q$ times after the invocation of init in each test case.
• This procedure should return the answer to the given query.

입력

출력

제한

• 1ドル ≤ N ≤ 200,円 000$
• 1ドル ≤ Q ≤ 100,円 000$
• $P[0] = -1$
• 0ドル ≤ P[i] < i$ for each $i$ such that 1ドル ≤ i < N$
• 0ドル ≤ W[i] ≤ 1,円 000,円 000$ for each $i$ such that 0ドル ≤ i < N$
• 1ドル ≤ L ≤ R ≤ 1,円 000,円 000$ in each query

서브태스크

힌트

예제

Consider the following calls:

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

The tree consists of 3ドル$ vertices, the root and its 2ドル$ children. All vertices 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 shaded rectangles) are illustrated below.

For every vertex $i$ (0ドル ≤ i < 3$), the sum of the coefficients of all vertices in the subtree of $i$ is equal to 1ドル$. Hence, this coefficient sequence is valid. The total cost is computed as follows:

Therefore the total cost is 3ドル$. This is the only valid coefficient sequence, therefore this call should return 3ドル$.

query(1, 2)

The minimum total cost for this query is 2ドル,ドル and is attained when the coefficient sequence is $[0, 1, 1]$.

샘플 그레이더

Input 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]

where $L[j]$ and $R[j]$ (for 0ドル ≤ j < Q$) are the input arguments in the $j$-th call to query. Note that the second line of the input contains only $N - 1$ integers, as the sample grader does not read the value of $P[0]$.

Output format:

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

where $A[j]$ (for 0ドル ≤ j < Q$) is the value returned by the $j$-th call to query.

첨부

• tree.zip