P17084 [COTS 2026] 滑雪 / Skijanje（暂无数据）

4s, 512M

Dominik 位于滑雪场的顶部。我们可以将滑雪场想象成一个有 $N$ 个节点的有根树，根节点为 $1$。对于每个大于 $1$ 的节点 $i$，其在树中的父节点为 $p_i$。每条边代表一条雪道，我们将雪道从 $1$ 到 $N - 1$ 编号，第 $i$ 条雪道通向节点 $i+1$。 每条雪道上都会举行一场比赛。第 $i$ 条雪道上的比赛从第 $l_i$ 分钟持续到第 $r_i$ 分钟，获胜者的奖金为 $c_i$。 Dominik 知道获胜者不一定是最好的滑雪者，但一定是最勇敢的滑雪者。由于他是最勇往直前的滑雪者，他参加的每一场比赛都肯定会获胜。 Dominik 在第 $0$ 分钟从节点 $1$ 出发，并沿某条路径从根节点向下移动。如果他在某条雪道上不参加比赛，他将瞬间通过，即花费 $0$ 分钟。Dominik 可以在节点处等待。如果他决定参加第 $i$ 条雪道上的比赛，那么他必须从第 $l_i$ 分钟开始到第 $r_i$ 分钟结束的时间内都在该雪道上，这样他就能赢得奖金 $c_i$。 回答 $Q$ 个**独立**问题：如果雪道 $k_i$ 上比赛的奖金变成 $x_i$，Dominik 最多能赢得多少奖金？注意，**这些问题是相互独立的，即问题之间奖金的变化不会保留**。

第一行是一个正整数 $N$（$2 \le N \le 5 \cdot 10^5$）。 第二行是 $N - 1$ 个正整数 $p_2, p_3, \dots, p_N$，依次为节点 $2, 3, \dots, N$ 的父节点。 在接下来的 $N - 1$ 行中，第 $i$ 行包含三个正整数 $l_i$, $r_i$ 和 $c_i$（$1 \le l_i \le r_i \le 10^9$，$1\le c_i\le 10^9$），描述第 $i$ 条雪道上的比赛。 下一行是一个正整数 $Q$（$1 \le Q \le 5 \cdot 10^5$），表示问题的数量。 在接下来的 $Q$ 行中，第 $i$ 行包含两个正整数 $k_i$ 和 $x_i$（$1\le k_i\le N-1$，$1 \le x_i \le 10^9$），描述第 $i$ 个问题。

对于每个问题，输出 Dominik 能够赢得的最大总奖金。

### 样例解释 以下为样例 $1$ 解释。 在第一个问题中，节点 2 和 3 之间雪道上的奖金变成了 1。Dominik 此时完成了节点 1 和 2 之间，以及 2 和 4 之间雪道上的比赛，因此他赢得了 $5 + 7 = 12$。 在第二个问题中，节点 2 和 4 之间雪道上的奖金变成了 20。Dominik 此时完成了节点 1 和 2 之间，以及 2 和 4 之间雪道上的比赛，因此他赢得了 $5 + 20 = 25$。 在第三个问题中，节点 1 和 2 之间雪道上的奖金变成了 100。Dominik 此时完成了节点 1 和 2 之间，以及 2 和 3 之间雪道上的比赛，因此他赢得了 $100 + 10 = 110$。 ::::align{center}  第二个问题：Dominik 在实线表示的雪道上完成比赛，不访问虚线表示的雪道。 :::: ### 子任务 | 子任务 | 分数 | 限制条件 | | :---: | :---: | :--- | | $1$ | $5 $ | $N, Q \le 200$ | | $2$ | $11$ | $N, Q \le 2000$ | | $3$ | $23$ | 对于每个问题 $i$，$x_i \ge c_{k_i}$ | | $4$ | $15$ | $N, Q \le 10^5$ | | $5$ | $30$ | 对于每个 $2 \le i \le N$，$p_i = i - 1$ | | $6$ | $16$ | 无附加限制条件。 |