题解

Difficulty：3.8 / Easy

假设图连通。不连通特判一下即可。

将题意转化成从 $1$ 出发，走 $L$ 步能不能到达 $a$。

首先 $\le L$ 的好做，跑单源最短路判一下即可。

现在考虑恰好 $L$ 步。显然得在一些环上来回走。

注意到无向图，每个点都有至少一个二元环连接。所以奇偶性相同的一定可以。

考虑建分层图，$f_{i,j}$ 为 $1\rarr i$ 经过奇/偶数条边最短路。显然实现方式和单源最短路一样。

namespace cjdst{
    void solve(){
		int n, m, q;
		std::cin >> n >> m >> q;
		std::vector <std::vector <int>> v(n + 5);
		for(int i = 1; i <= m; i++){
			int x, y;
			std::cin >> x >> y;
			v[x].push_back(y);
			v[y].push_back(x);
		}
		std::vector <std::vector <int>> dis(n + 5, std::vector <int>(2, 0x3f3f3f3f));
		std::queue <pii> qq;
		dis[1][0] = 0;
		qq.push({1, 0});
		while(!qq.empty()){
			auto head = qq.front();
			qq.pop();
			for(int i:v[head.first]){
				if(dis[i][head.second ^ 1] != 0x3f3f3f3f) continue;
				dis[i][head.second ^ 1] = dis[head.first][head.second] + 1;
				qq.push({i, head.second ^ 1});
			}
		}
		while(q--){
			int x, y;
			std::cin >> x >> y;
			if(dis[x][y % 2] <= y) std::cout << "Yes\n";
			else std::cout << "No\n";
		}
	}
}

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