Problem 3. Ski Slope

USACO 2025 US Open Contest, Silver

Bessie 要和她的朋友们去滑雪旅行。山上有 $N$ 个标记点（$1\leq N \leq 10^5$），编号为 $1, 2, \ldots, N$，以海拔升序排列（标记点 $1$ 位于山脚下）。

对于每一个标记点 $i > 1$，都有一条雪道开始于标记点 $i$，结束于标记点 $p_i$（$1\le p_i<i$）。这条雪道的难度为 $d_i$（$0 \leq d_i \leq 10^9$），乐趣值为 $e_i$（$0 \leq e_i \leq 10^9$）。

Bessie 的 $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$ 的每一个 $i$，以下一行包含三个空格分隔的整数 $p_i$，$d_i$ 和 $e_i$。

以下一行包含 $M$。

以下 $M$ 行，每行包含两个空格分隔的整数 $s_j$ 和 $c_j$。

输出格式（输出至终端 / 标准输出）：

输出 $M$ 行，对于每一个朋友输出一行，包含对于该朋友的答案。
注意这个问题涉及到的整数可能需要使用 64 位整数类型（例如，C/C++ 中的 "long long"）。

输入样例：

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

输出样例：

0
300
500
300
500
500
300
500

1. 第一个朋友不能从除了 $1$ 以外的任何标记点开始，因为任何其他标记点都会导致她们经过至少一条难度大于 $19$ 的雪道。她们的总乐趣值为 $0$。
2. 第二个朋友可以从标记点 $4$ 开始，滑到标记点 $2$，然后到 $1$。她们的总乐趣值为 $100+200=300$。她们经过了一条难度大于 $19$ 的雪道。
3. 第三个朋友可以从标记点 $3$ 开始，滑到标记点 $2$，然后到 $1$。她们的总乐趣值为 $300+200=500$。她们经过了两条难度大于 $19$ 的雪道。

测试点性质： 测试点 2-4：$N, M\le 1000$。测试点 5-7：所有 $c_j=0$。测试点 8-17：没有额外限制。

供题：Brandon Wang