题解

核心思路：奇偶分层最短路

把每个工人拆成“走了偶数条边”和“走了奇数条边”两个状态，从 1 号工人做 BFS。询问 (a,L) 可行，当且仅当到达 a 且路径长度奇偶性为 L mod 2 的最短距离不超过 L。无向边允许来回走两步，因此之后可补任意偶数长度。

算法流程

1. 读入题目给出的全部数据，并初始化核心状态。
2. 执行本题的关键处理：把每个工人拆成“走了偶数条边”和“走了奇数条边”两个状态，从 1 号工人做 BFS。询问 (a,L) 可行，当且仅当到达 a 且路径长度奇偶性为 L mod 2 的最短距离不超过 L。无向边允许来回走两步，因此之后可补任意偶数长度。
3. 根据最终状态输出答案。边界、计数和中间结果使用能够覆盖题目上限的数据类型；完整实现见 std/main.cpp。

正确性说明

核心状态只保存影响后续决策的全部信息；每次转移（或贪心选择）都与题意中的一次合法操作一一对应，且不会遗漏更优候选。因此处理结束时得到的状态恰好覆盖全部合法方案，其中所取最优值就是题目要求的答案。

复杂度

• 时间复杂度：$O(n+m+q)$
• 空间复杂度：$O(n+m)$