Ski Slope

题目描述

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$），这会限制他们只能选择某个起始路标点，使得他们所经过的滑道中，难度严格大于 $s_j$ 的滑道数量最多为 $c_j$。 对于每个朋友，计算他们能获得的最大乐趣值。

输入格式

第一行包含 $N$。 然后对每个 $i$ 从 $2$ 到 $N$，接下来一行包含三个用空格分隔的整数 $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$ 以外不能从任何路标点开始，因为从其他任何路标点出发都会导致他们至少经过一条难度大于 $19$ 的滑道。他们的总乐趣值为 $0$。 第二个朋友可以从路标点 $4$ 开始，沿滑道下到路标点 $2$，再到 $1$。他们的总乐趣值为 $100+200=300$。他们经过了 $1$ 条难度大于 $19$ 的滑道。 第三个朋友可以从路标点 $3$ 开始，沿滑道下到路标点 $2$，再到 $1$。他们的总乐趣值为 $300+200=500$。他们经过了 $2$ 条难度大于 $19$ 的滑道。 评分（SCORING）： 输入 2-4：$N, M\le 1000$ 输入 5-7：所有 $c_j=0$ 输入 8-17：无额外限制。 题目来源：Brandon Wang

标签: USACO|2025|Silver

来源

USACO|2025|Silver