P11051 [IOI 2024] Cost on a Tree

When submitting, please do not include `tree.h`. Please do not submit using C++14 (GCC 9).

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 P, std::vector 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.

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]$.

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`.

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: | Node | Weight | Coefficient | Cost | | :----: | :----: | :---------: | :------------------------: | | $0$ | $1$ | $-1$ | $\mid -1 \mid \cdot 1 = 1$ | | $1$ | $1$ | $1$ | $\mid 1 \mid \cdot 1 = 1$ | | $2$ | $1$ | $1$ | $\mid 1 \mid \cdot 1 = 1$ | 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$ | Subtask | Points | Additional Constraints | | :-----: | :---: | ------------------------------------------------------------ | | 1 | $10$ | $Q \leq 10$; for all $i$ with $1 \leq i < N$, $W[P[i]] \leq W[i]$ | | 2 | $13$ | $Q \leq 10$; $N \leq 2\,000$ | | 3 | $18$ | $Q \leq 10$; $N \leq 60\,000$ | | 4 | $7$ | For all $i$ with $0 \leq i < N$, $W[i] = 1$ | | 5 | $11$ | For all $i$ with $0 \leq i < N$, $W[i] \leq 1$ | | 6 | $22$ | $L = 1$ | | 7 | $19$ | No additional constraints. | Translated by ChatGPT 5