题目分析

我们有一张连通无向图，零件从 1 号点出发，每次可以沿一条边走到相邻点。
有多次询问：能否恰好走 L 步到达 a 号点？

L 最大到 10^9，不能直接模拟。

---

核心思路：步数可以增加 2

观察一个关键性质：

如果从 1 号点出发，存在一条长度为 d 的路径到达 a 号点，
那么对于任意非负整数 k，一定存在长度为 d + 2k 的路径到达 a 号点。

原因很简单：可以在任意一条边上“来回走一次”：

从 a 走到相邻点 b，再从 b 走回 a

这样位置没有变，但步数增加了 2。

例如：

1 -> 2 -> 3        // 2步到达3
1 -> 2 -> 3 -> 2 -> 3   // 4步到达3，在边 3-2 上走了一个来回

因此，只需要知道到达每个点的最短偶数步路径和最短奇数步路径，
其它更长的同奇偶步数都可以通过“来回走”补齐。

---

算法设计：奇偶最短路

定义：

• dis[x][0]：从 1 号点出发，走偶数步到达 x 号点的最短步数。
• dis[x][1]：从 1 号点出发，走奇数步到达 x 号点的最短步数。

对于询问 (a, L)：

1. 令 p = L % 2，即 L 的奇偶性。
2. 如果 dis[a][p] <= L，则说明可以恰好走 L 步到达 a 号点。
   • 先走最短奇偶路径到达 a。
   • 剩余步数 L - dis[a][p] 是偶数。
   • 这些偶数步可以通过在边上“来回走”消耗掉。
3. 否则，输出 No。

---

BFS 求奇偶最短路

因为每条边长度都是 1，可以用 BFS。

普通 BFS 只记录一个点是否访问过，但这里需要同时记录到达该点时的步数是奇数还是偶数。

状态定义

queue<pair<int, int>> q;  // {当前点, 当前步数}

初始化

dis[1][0] = 0;        // 起点1号点，走0步，0是偶数
q.push({1, 0});

转移

从队列中取出状态 (u, step)：

• 当前在点 u，已经走了 step 步。
• 对于 u 的每个相邻点 v：
  • 走一步到 v，新步数 next_step = step + 1。
  • 新步数的奇偶性：next_step % 2。
  • 如果 next_step < dis[v][next_step % 2]，则更新它，并将新状态入队。

因为 BFS 是按步数递增的顺序遍历的，所以每个状态第一次到达时就是最短路径。

---

代码实现

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;
int n, m, q;
vector<int> e[N];               // 邻接表存图
int dis[N][2];                  // dis[x][0]：偶数步到达x的最短步数
                                // dis[x][1]：奇数步到达x的最短步数

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m >> q;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }

    // 初始化最短路数组为一个很大的值
    memset(dis, 0x3f, sizeof(dis));

    // 起点：1号点，走了0步（偶数）
    dis[1][0] = 0;

    queue<pair<int, int>> que;  // 队列元素：{当前点, 当前步数}
    que.push({1, 0});

    // BFS
    while (!que.empty()) {
        pair<int, int> cur = que.front();
        que.pop();
        int u = cur.first;      // 当前点
        int step = cur.second;  // 当前步数

        // 遍历所有相邻点
        for (int v : e[u]) {
            int next_step = step + 1;       // 走一步
            int parity = next_step % 2;     // 新步数的奇偶性

            // 如果发现更短的奇偶路径，则更新并入队
            if (next_step < dis[v][parity]) {
                dis[v][parity] = next_step;
                que.push({v, next_step});
            }
        }
    }

    // 处理每个询问
    while (q--) {
        int a, L;
        cin >> a >> L;
        int parity = L % 2;   // 询问步数的奇偶性

        // 如果到达a的对应奇偶最短步数不超过L，则可以恰好到达
        if (dis[a][parity] <= L)
            cout << "Yes\n";
        else
            cout << "No\n";
    }

    return 0;
}

---

样例模拟

样例图是一个五边形：

1 - 2
|   |
5 - 4 - 3

边为：1-2, 2-3, 3-4, 4-5, 5-1

BFS 求出的奇偶最短路大致如下：

点	dis[x][0] 偶数最短	dis[x][1] 奇数最短
1	0	5
2	4	1
3	2	3
4
5	4	1

询问判断：

1 0  -> 偶数，dis[1][0]=0 <= 0，Yes
2 1  -> 奇数，dis[2][1]=1 <= 1，Yes
3 1  -> 奇数，dis[3][1]=3 >  1，No
4 4  -> 偶数，dis[4][0]=2 <= 4，Yes
5 5  -> 奇数，dis[5][1]=1 <= 5，Yes

与样例输出一致。

---

复杂度分析

• 每个点有两种状态：偶数步到达、奇数步到达，所以最多有 2n 个状态。
• 每条边在 BFS 中会被访问常数次。
• 总时间复杂度：O(n + m + q)
• 空间复杂度：O(n + m)

在 n, m, q <= 10^5 的数据范围内可以高效通过。

---

总结

本题的关键是发现“来回走”可以增加 2 步而不改变位置，从而将问题转化为求到达每个点的奇数最短路径和偶数最短路径。
通过 BFS 同时维护两种奇偶状态，最后在 O(1) 时间内回答每个询问。