您是一位极限运动家，正挑战一片由计算机生成的、结构奇特的数字山脉。 这片山脉由 个山峰组成，每个山峰都有其独特的海拔高度。 您的目标是规划出一条最长的、符合“极限跳跃”规则的下山路径。 这片数字山脉的结构可以用一棵二叉树来精确描述。您规划的路径必须遵循一系列严格的规则，我们称之为一条“极限交替路径”： 路径方向 : 路线必须严格自上而下，即只能从一个山峰移动到与之直接相连的子山峰。 严格交替 : 路径上海拔的变化必须是严格的交替上升和下降。例如，一条合法的路径可以是海拔 ，其海拔序列满足 p_3 。无论是“先升后降”还是“先降后升”的交替模式都是允许的。 极限跳跃 : 每次移动（从一个山峰到下一个）的海拔绝对差值必须大于或等于一个给定的阈值 。形式化地，对于路径上任意相邻的两个山峰 和 ，必须满足 。 您的任务是找出在这片山脉中，能够规划出的最长“极限交替路径”的长度。路径的长度以其所包含的山峰数量计算。
输入描述:
第一行包含两个整数 和 。 是山峰的总数, 。 是要求的最小海拔差 (极限跳跃阈值), 。接下来的 行描述了山脉的结构。每行包含三个整数 ： 是当前山峰的海拔。 是其左侧子山峰的海拔。 是其右侧子山峰的海拔。如果某个子山峰不存在，则用 表示。所有山峰的海拔高度都在 范围内，且保证互不相同。这 行的输入顺序遵循该山脉地图的先序遍历顺序。
输出描述:
一个整数，代表最长“极限交替路径”的长度。
示例1
输入
6 10
20 10 -1
10 21 -1
21 -1 11
11 -1 22
22 12 -1
12 -1 -1
备注:
本题由牛友@Charles 整理上传
加载中...