🧩 题意解析
工厂有 n 个工人，某些工人之间有双向传送带。
如果编号为 x 的工人要生产一个 第 L 阶段 的零件：
- 当 L = 1：所有与 x 相邻的工人必须给他提供“原材料”
- 当 L > 1：所有与 x 相邻的工人必须生产 L−1 阶段 的零件（递归）
1 号工人（轩轩）想知道：
对于每张工单 (a, L)，他是否需要被迫提供原材料？
最终我们需要回答 Q 个查询：“Yes / No”。
🔍 问题转化
若想知道“工人 a 的第 L 阶段是否会需要 1 号工人提供原材料”，需要理解：
一个工人需要原材料的时机：
他生产 第 1 阶段 的零件时。
L 阶段如何递减？
从 a 开始，每条边都会使阶段数 L 减 1，直到减到 1。
因此：
轩轩是否会提供原材料 = 是否存在从 a 到 1 的路径，使得路径长度 <= L 且 (L − 路径长度) = 1
化简形式：
路径长度 d == L - 1
markdown 复制代码
也就是说：
从 1 到 a 的最短路径长度的奇偶性与 L 的奇偶性必须一致，并且距离 ≤ L。
🌟 关键结论（最重要）
我们只需要：
- 从
1号工人出发 - 计算所有点到 1 的最短距离，并且要区分 奇数步 和 偶数步
定义：
dis[x][0]= 到 x 的“偶数步”最短距离dis[x][1]= 到 x 的“奇数步”最短距离
查询时判断：
如果 dis[a][L % 2] <= L，则轩轩需要提供原材料（Yes） 否则 No
yaml 复制代码
🚀 为什么只需要 BFS？
所有边权都是 1。
但是需要区分“奇偶层数”，于是我们让每个点有两种状态：
- 到达该点走了偶数条边
- 到达该点走了奇数条边
因此 dis 数组大小是 n × 2。
算法复杂度：
O(n + m + q)
yaml 复制代码
完全满足要求。
🧠 证明（简述）
工人 a 想生产第 L 阶段 → 必须沿着图的边递减 L 次直到成为 1 阶段。
最终到达某工人 k 时，需要提供原材料的条件是：
k 与 a 的距离 = L - 1
复制代码
特别地，如果最终 k = 1（轩轩），则说明：
从 a 到 1 的距离 d = L - 1 → d <= L 且 (d % 2 == L % 2)
这与我们的 dis 数组判断方式一致。
✅ AC 代码（可直接使用）
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
const int MAXN = 100005;
int n, m, q;
vector<int> g[MAXN];
int dis[MAXN][2]; // dis[x][0] = 偶数步最短路, dis[x][1] = 奇数步最短路
void bfs(int s) {
queue<int> que;
memset(dis, 0x3f, sizeof(dis));
dis[s][0] = 0; // 从 1 号工人开始，走 0 条边（偶数）
que.push(s);
while (!que.empty()) {
int u = que.front();
que.pop();
for (int v : g[u]) {
// 当前从 u 到 v 是一条边（奇偶互换）
if (dis[v][1] > dis[u][0] + 1) {
dis[v][1] = dis[u][0] + 1;
que.push(v);
}
if (dis[v][0] > dis[u][1] + 1) {
dis[v][0] = dis[u][1] + 1;
que.push(v);
}
}
}
}
int main() {
scanf("%d %d %d", &n, &m, &q);
for (int i = 1; i <= m; i++) {
int u, v;
scanf("%d %d", &u, &v);
g[u].push_back(v);
g[v].push_back(u);
}
bfs(1);
while (q--) {
int a, L;
scanf("%d %d", &a, &L);
if (dis[a][L & 1] <= L)
printf("Yes\n");
else
printf("No\n");
}
return 0;
}
'''