# 题解：树上的容限路径

贡献：Codex（GPT-6）补齐规格，给出可行末边权集合的树遍历、证明、实现与验证。

## 路线只能沿唯一简单路径

基础图是一棵树。任何重复顶点的非空行走都必须重复某条树边，故合法路线一定是简单路径。固定起点后，每个终点的基础路径唯一；只需考虑沿途如何选择特殊边。

将每条树边上的特殊边权排序、去重。对一个固定起点，将树看成以它为根。为每个可达顶点 $u$ 保存集合 $S_u$ ：沿根到 $u$ 的路径合法到达时，最后一条特殊边可能具有的所有权值。

起点的第一条边不受容限约束，因此邻接边的全部权值都是候选。对于其他顶点 $u$ 到孩子 $v$ 的特殊边权 $w$ ，保留它当且仅当

$$S_u\cap[w-R_u,w-L_u]\ne\varnothing.$$

在已排序的 $S_u$ 中查找首个不小于 $w-R_u$ 的元素，再检查其是否不大于 $w-L_u$ .孩子的权值按排序顺序扫描，所得 $S_v$ 自然有序。若它为空，整棵后继子树无需继续遍历。

## 正确性

对深度归纳。第一层所有候选均可直接到达，集合准确。假设 $S_u$ 准确，权值 $w$ 能扩展某条合法路径，当且仅当存在合法前驱末权值 $p\in S_u$ 满足 $L_u\le w-p\le R_u$ ，这正是上述区间相交条件。所以计算出的 $S_v$ 不漏也不多。集合非空的顶点恰好可达，再加上起点即为答案。分别更换起点即可求出全部答案。

不能只保存最小、最大可行权值。例如 $S_u=\{0,2\}$ 且容限为 $[0,0]$ 时，下一条权值1不可用。也不能把可达关系当作无向：正容限的反向转换可能不合法。

## 复杂度与实现

设 $n$ 为顶点数，$m$ 为特殊边数。排序总时间 $O(m\log(m+1))$ .对每个起点，每条树边至多访问一次，每个特殊边权至多检查一次；二分最多 $O(\log(m+1))$ ，所以总时间

$$O(m\log(m+1)+n(n+m\log(m+1))).$$

同一次遍历中，每个非根顶点的候选集合来自其唯一父边，集合大小总和不超过 $m$ ，故空间 $O(n+m)$ .使用显式队列避免长链递归；用64位整数计算权差和区间端点。

[std.cpp](std.cpp) 给出完整实现。逐路径枚举全部特殊边选择可作为小规模检查器，但分支数会指数增长。只存区间端点的方案不正确；这两种思路不作为完整数据的补充算法。

## 性能

正式数据每份运行五次并另测峰值。标准程序最慢中位数 0.330252 秒，峰值 6.05 MiB；按2倍取整到0.5秒，时限为 1 秒。 [环境说明](../../../docs/评测环境与性能.md)与[逐次测量](../../../docs/benchmark-R34.json)可供复现；其他环境需重新校准。