会员专享
请先
登录，登录后可使用今日免费解锁；
开通会员后可解锁完整内容。
解题思路
本题要在一棵二叉树上，从根节点 1 出发走到某个叶子节点，要求路径的「海拔跨度」（路径上最大的 value 减最小的 value）不超过 S；在满足该条件的路线中取总体力消耗最小者，消耗相同时取节点 id 序列字典序最小者。这是一道 DFS（深度优先搜索）+ 路径状态维护 的题。
关键观察一：路径信息可以沿 DFS 一次推完。 判断一条路线是否合法、消耗多少，只需要三个量：路径上出现过的最高海拔 hi、最低海拔 lo、累计消耗 cost。从父节点走到子节点 ch 时有
hi' = max(hi, value[ch])，lo' = min(lo, value[ch])；- 高差
d = value[ch] - value[parent]，cost' = cost + (alpha * d)（d>0，上坡）或 cost + beta * (-d)（d<0，下坡）。
