P12027 [USACO25OPEN] Ski Slope S

题目描述

贝茜要和朋友们一起去滑雪。雪山上有 $N$ 个路标（$1 \leq N \leq 10^5$），按海拔从低到高依次标记为 $1, 2, \ldots, N$（路标 $1$ 位于山脚）。

对于每个路标 $i > 1$，有一条从路标 $i$ 出发，终点为路标 $p_i$（$1 \leq p_i < i$）的滑雪道。这条滑道的难度为 $d_i$（$0 \leq d_i \leq 10^9$），乐趣值为 $e_i$（$0 \leq e_i \leq 10^9$）。

贝茜的 $M$ 个朋友（$1 \leq M \leq 10^5$）每人会进行如下操作：选择一个起始路标 $i$，然后沿着滑道向下滑行（依次经过 $p_i,p_{p_i}$，依此类推），直到抵达路标 $1$。

每位朋友获得的乐趣值等于他们经过的所有滑道的乐趣值之和。每个朋友有不同的技能水平 $s_j$（$0 \leq s_j \leq 10^9$）和勇气值 $c_j$（$0 \leq c_j \leq 10$），这限制他们选择的起始路标必须满足：滑行过程中最多有 $c_j$ 条滑道的难度超过 $s_j$。

请为每位朋友计算他们能获得的最大乐趣值。

输入格式

第一行包含 $N$。

接下来 $2$ 到 $N$ 行，每行包含三个整数 $p_i$，$d_i$ 和 $e_i$。

随后一行包含 $M$。

接下来 $M$ 行，每行包含两个整数 $s_j$ 和 $c_j$。

输出格式

输出 $M$ 行，每行对应一个朋友的答案。

注意：由于涉及大整数运算，可能需要使用 64 位整数类型（如 C/C++ 中的 long long）。

输入输出样例 #1

输入 #1

4
1 20 200
2 30 300
2 10 100
8
19 0
19 1
19 2
20 0
20 1
20 2
29 0
30 0

输出 #1

0
300
500
300
500
500
300
500

说明/提示

第一位朋友只能选择路标 $1$ 作为起点，因为其他路标都会导致至少经过一条难度超过 $19$ 的滑道。总乐趣值为 $0$。

第二位朋友可以选择路标 $4$，依次滑行至路标 $2$ 和 $1$。总乐趣值为 $100 + 200 = 300$，其中有一条滑道难度超过 $19$。

第三位朋友可以选择路标 $3$，依次滑行至路标 $2$ 和 $1$。总乐趣值为 $300 + 200 = 500$，其中有两条滑道难度超过 $19$。

• 测试点 $2\sim4$：$N, M \leq 1000$。
• 测试点 $5\sim7$：所有 $c_j = 0$。
• 测试点 $8\sim17$：无额外限制。