解法思路

核心思想：分类处理 + 树上差分

根据油箱容量 $k$ 的大小采用不同的优化策略：

• 大 $k$ ($k > B$)：路径上加油点稀疏，直接模拟
• 小 $k$ ($k \leq B$)：路径上加油点密集，使用前缀和优化

算法框架

1. 预处理

• LCA 预处理：使用倍增法预处理每个节点的 $2^i$ 级祖先，用于快速求两点间路径
• DFS 序与深度：记录每个节点的深度信息

2. 大 $k$ 处理 ($k > B$)

• 从路径起点和终点分别向 LCA 方向模拟跳跃
• 每次跳跃 $k$ 条边，累加经过节点的加油成本
• 使用 DFS 栈记录路径，快速找到 $k$ 级祖先

3. 小 $k$ 处理 ($k \leq B$)

• 对每个 $k$ 值单独处理
• 在 DFS 过程中维护前缀和数组 sum[x]，记录从根节点到 $x$ 路径上每隔 $k$ 个节点的成本之和
• 利用前缀和快速计算任意路径上的加油成本

关键技巧

1. LCA 优化：$O(\log n)$ 时间求任意两点最近公共祖先
2. 分类处理：设定阈值 $B = 200$，平衡时间与空间复杂度
3. 树上差分：对小 $k$ 使用前缀和技巧，$O(1)$ 计算路径成本
4. DFS 栈：记录当前 DFS 路径，快速访问 $k$ 级祖先

复杂度分析

• 时间复杂度：$O(n \log n + nB)$，其中 $B$ 为阈值
• 空间复杂度：$O(n \log n + nB)$