题目解法概述

主要思路

本题的核心是处理树上路径上的收费站选择问题，需要在金币和银币两种支付方式间做出最优决策，使得最终保留的金币数量最大化。

关键观察

1. 路径确定：由于树的结构，任意两点间的路径是唯一的
2. 收费站的独立性：每个收费站可以独立选择支付金币（1枚）或银币（$C_j$枚）
3. 目标函数：最大化保留的金币数，等价于最小化消耗的金币数

算法步骤

1. 预处理

• 建立树的邻接表表示
• 计算每个节点的深度、父节点信息（用于LCA查询）
• 预处理每个收费站的信息（所在道路、银币费用）

2. 路径信息收集

对于每个查询$(S_k, T_k)$：

• 找到路径上的所有收费站
• 收集这些收费站的银币费用$C_j$

3. 贪心策略

设路径上有$L$个收费站，每个收费站的银币费用为$C_1, C_2, ..., C_L$：

1. 将收费站的银币费用按升序排序
2. 从银币费用最小的收费站开始，尽量使用银币支付
3. 计算能够用银币支付的收费站数量：
   • 累计所需银币总数，直到超过公民拥有的银币数$Y_k$
   • 或者遍历完所有收费站
4. 设能用银币支付的收费站数量为$cnt$，则需要用金币支付的收费站数量为$L - cnt$

4. 可行性判断与答案计算

设：

• $X$ = 公民拥有的金币数
• $Y$ = 公民拥有的银币数
• $L$ = 路径上的收费站总数
• $cnt$ = 能用银币支付的收费站数量

则：

1. 可行性条件：$X + cnt \ge L$（即总资源足够支付所有收费站）
2. 最大保留金币数：如果可行，则为$X - (L - cnt)$

时间复杂度优化

• 使用倍增法或Tarjan算法进行LCA查询，单次$O(\log N)$
• 路径上收费站信息的收集可以通过树上差分预处理
• 总时间复杂度：$O((N+M+Q)\log N)$

算法总结

对于每个查询：

1. 找到路径$S_k \to T_k$上的所有收费站
2. 将这些收费站的银币费用排序
3. 贪心地用银币支付费用最小的收费站
4. 判断剩余的金币是否足够支付其他收费站
5. 计算最终能保留的金币数量

边界情况处理

1. 如果路径上没有收费站：直接返回$X_k$（不消耗金币）
2. 如果银币足够支付所有收费站：返回$X_k$（全用银币支付）
3. 如果金币不足：返回$-1$（不可行）

核心公式

设排序后的银币费用为$sorted_C[1..L]$， 找到最大的$cnt$使得：

$$\sum_{i=1}^{cnt} sorted_C[i] \le Y_k$$

则答案为：

$$\text{ans} = \begin{cases} X_k - (L - cnt) & \text{if } X_k + cnt \ge L \\ -1 & \text{otherwise} \end{cases} $$