P14772 [ICPC 2024 Seoul R] Protecting Kingdom

在 **CPIC**（公共基础设施保护委员会）王国中，有 $n$ 个村庄，编号从 1 到 $n$，它们通过 $n-1$ 条道路连接，形成一个树状结构。每条道路连接两个村庄，并具有正的长度。具体来说，第 $i$ 条道路连接村庄 $i+1$ 与村庄 $p_i$ ($1 \leq p_i \leq i$)，长度为 $l_i$。由于地形险峻且发生过事故，这些道路上的某些点被标记为危险点。 在第 $i$ 条道路上，有 $k_i$ 个危险点，位于距离村庄 $p_i$ 特定距离 $x_{i,1}, x_{i,2}, \dots, x_{i,k_i}$ 处，满足 $0 < x_{i,1} < x_{i,2} < \cdots < x_{i,k_i} < l_i$。这些距离为整数，表示沿道路的位置。 新成立的 **CPIC** 安全委员会希望通过部署一项保护措施来提升旅行者的安全。他们可以选择道路上的任意两点（包括村庄），并保护它们之间的最短路径。这条路径可以覆盖位于其上（包括端点）的所有危险点，且其长度不得超过给定的长度 $w$。 给定道路网络、危险点的位置以及允许的最大路径长度 $w$，请编写一个程序，确定通过最优选择两个点并保护它们之间长度 $\leq w$ 的最短路径所能覆盖的危险点的最大数量。

你的程序需要从标准输入读取数据。输入的第一行包含两个整数 $n$ 和 $w$ ($2 \leq n \leq 250,000$, $1 \leq w \leq 10^{18}$)，其中 $n$ 是村庄的数量，$w$ 是允许的保护路径的最大长度。接下来的 $n-1$ 行中，第 $i$ 行提供关于第 $i$ 条道路的信息，以三个整数 $p_i$, $l_i$, $k_i$ 开头 ($1 \leq p_i \leq i$, $1 \leq l_i \leq 10^{12}$, $k_i \geq 0$)，其中 $p_i$ 是通过该道路与村庄 $i+1$ 连接的村庄，$l_i$ 是道路的长度，$k_i$ 是道路上的危险点数量。如果 $k_i > 0$，则该行后面跟着 $k_i$ 个整数 $x_{i,1}, x_{i,2}, \dots, x_{i,k_i}$ ($0 < x_{i,1} < x_{i,2} < \cdots < x_{i,k_i} < l_i$)，表示从村庄 $p_i$ 到道路上每个危险点的距离。危险点的总数 $k_1 + k_2 + \cdots + k_{n-1}$ 不超过 $10^6$。

你的程序需要向标准输出写入结果。输出恰好一行。该行应包含通过选择道路上任意两点并保护它们之间长度不超过 $w$ 的最短路径所能覆盖的危险点的最大数量。

翻译由 DeepSeek V3 完成