P17084 [COTS 2026] Skiing / Skijanje (No testdata)

4s, 512M

Dominik is at the top of the ski resort. We can think of the ski resort as a rooted tree with $N$ nodes, with node $1$ as the root. For each node $i > 1$, its parent in the tree is $p_i$. Each edge represents a ski slope. We number the slopes from $1$ to $N - 1$, and slope $i$ leads to node $i + 1$. A race is held on each slope. The race on slope $i$ lasts from minute $l_i$ to minute $r_i$, and the prize for the winner is $c_i$. Dominik knows that the winner is not necessarily the best skier, but must be the bravest skier. Since he is the most fearless skier, he will definitely win every race he participates in. Dominik starts from node $1$ at minute $0$ and moves downward along some path from the root. If he does not participate in the race on a slope, he passes through it instantly, i.e. it takes $0$ minutes. Dominik may wait at nodes. If he decides to participate in the race on slope $i$, then he must stay on that slope for the entire time interval from minute $l_i$ to minute $r_i$, so that he can win the prize $c_i$. Answer $Q$ **independent** queries: if the prize on slope $k_i$ becomes $x_i$, what is the maximum total prize Dominik can win? Note that **these queries are independent, i.e. the prize changes do not carry over between queries**.

The first line contains a positive integer $N$ ($2 \le N \le 5 \cdot 10^5$). The second line contains $N - 1$ positive integers $p_2, p_3, \dots, p_N$, the parent of nodes $2, 3, \dots, N$, respectively. In the next $N - 1$ lines, line $i$ contains three positive integers $l_i$, $r_i$, and $c_i$ ($1 \le l_i \le r_i \le 10^9$, $1 \le c_i \le 10^9$), describing the race on slope $i$. The next line contains a positive integer $Q$ ($1 \le Q \le 5 \cdot 10^5$), the number of queries. In the next $Q$ lines, line $i$ contains two positive integers $k_i$ and $x_i$ ($1 \le k_i \le N - 1$, $1 \le x_i \le 10^9$), describing the $i$-th query.

For each query, output the maximum total prize Dominik can win.

### Sample Explanation Below is the explanation for sample $1$. In the first query, the prize on the slope between nodes 2 and 3 becomes 1. Dominik then completes the races on the slopes between nodes 1 and 2, and between 2 and 4, so he wins $5 + 7 = 12$. In the second query, the prize on the slope between nodes 2 and 4 becomes 20. Dominik then completes the races on the slopes between nodes 1 and 2, and between 2 and 4, so he wins $5 + 20 = 25$. In the third query, the prize on the slope between nodes 1 and 2 becomes 100. Dominik then completes the races on the slopes between nodes 1 and 2, and between 2 and 3, so he wins $100 + 10 = 110$. ::::align{center}  In the second query, Dominik completes races on the solid-line slopes and does not visit the dashed-line slopes. :::: ### Subtasks | Subtask | Score | Constraints | | :---: | :---: | :--- | | $1$ | $5$ | $N, Q \le 200$ | | $2$ | $11$ | $N, Q \le 2000$ | | $3$ | $23$ | For each query $i$, $x_i \ge c_{k_i}$ | | $4$ | $15$ | $N, Q \le 10^5$ | | $5$ | $30$ | For each $2 \le i \le N$, $p_i = i - 1$ | | $6$ | $16$ | No additional constraints. | Translated by ChatGPT 5