这道题，我在考场上~~荣获30分~~。

CODE

如下：

#include<bits/stdc++.h>
using namespace std;
struct edge
{
	int nxt,end;
}e[100000*2+5];
int cnt=0,head[100000+5];
int p1[100000+5],p2[100000+5],n,m,T;
queue<int>q;
inline void add(int a,int b)
{
	e[++cnt]=(edge){head[a],b};
	head[a]=cnt;
}
void bfs(int a)
{
	q.push(a);p1[a]=0;
	while(!q.empty())
	{
		int now=q.front();
		q.pop();
		for(int i=head[now];i;i=e[i].nxt)
		{
			int to=e[i].end;
			if(p1[to]==-1&&p2[to]==-1)
			{
				p1[to]=p1[now]+1;
				q.push(to);
			}
			else if(p1[to]!=-1&&p2[to]==-1)
			{
				if(p1[now]%2==p1[to]%2&&p1[now]!=-1)
					p2[to]=p1[now]+1;
				else if(p2[now]%2==p1[to]%2&&p2[now]!=-1)
					p2[to]=p2[now]+1;
				else
					continue;
				q.push(to);
			}
			else
			{
				continue;
			}
		}
	}
	return;
}
int main()
{
	int a,b;
	scanf("%d%d%d",&n,&m,&T);
	memset(p1,-1,sizeof(p1));
	memset(p2,-1,sizeof(p2));
	for(int i=1;i<=m;i++)
		scanf("%d%d",&a,&b),add(a,b),add(b,a);
	bfs(1);
	for(int i=1;i<=T;i++)
	{
		scanf("%d%d",&a,&b);
		if(p1[a]%2==b%2&&p1[a]!=-1&&p1[a]<=b)
			printf("Yes\n");
		else if(p2[a]%2==b%2&&p2[a]!=-1&&p2[a]<=b)
			printf("Yes\n");
		else
			printf("No\n");
	}
	return 0;
}

思路

考虑这样一个图，边权均为 1：

现在，询问 2 号工人要生产等级为 6 的零件，1 号是否提供原材料。

答案当然是肯定的，因为存在从 2 到 1 的偶数长路径（2->6->5->4->3->2->1，长度 6），且比 6 大或相等。

为什么呢？

推理

我们可以想到：

我们要取每个节点到 1 号节点奇/偶长度路径最短的值（ $p_1$ ， $p_2$ ）。
如果，一个节点的生产等级（ $l$ $l$ ）大于等于 $p_i$ $p_{i}$ （指 $p_1$ $p_{1}$ ， $p_2$ $p_{2}$ 中的任意一个，满足一个就行），且等级与 $p_i$ $p_{i}$ 奇偶性相同，则 1 需要提供原材料：
- 当相同时，毋庸置疑，1 一定提供原材料。
- 当大于 $p_i$ 时，若与 $p_i$ 奇偶性相同，则可以实现 1 与旁边的任意一个节点轮换生产，最终轮到 1 生产原材料。

进一步推理，有以下三种情况：

$l < \min(p_1,p_2)$ ：轮不到 1 生产，No。
$\min(p_1,p_2)\le l < \max(p_1,p_2)$ ：如果 $l = \min(a_1,a_2) \pmod 2$ ，Yes，否则No。
$l \ge \max(p_1,p_2)$ ：可以实现 1 与旁边的任意一个节点轮换生产，最终轮到 1 生产原材料。Yes。

求 $p_1$ 与 $p_2$

因为边权均为 1 ，所以使用 bfs 求解，时间复杂度 $O(n+m)$ 。

先将d1[]d2[]数组初始化为 -1 ，表示未求解。1 号节点的d1[]值为 0 。

由一号节点开始拓展。蓝色的是p1[]的值。

规则是，当遇到下一个节点的p1[]的值为 -1 时，则p1[]的值为现在的p1[]的值加一，然后将下一个节点压入队列。

现在似乎拓展完了。但是，我们仅仅求出了p1[]数组。

再增加规则：设拓展节点为 u ，被拓展节点为 v ，如果p1[v]值不为 -1 ，但p2[v]的值为 -1 ，则

如果p1[u]==p1[v]（这样保证p1[]p2[]奇偶性不同），这样p2[v]=p1[u]+1。然后将 v 压入队列。
如果p2[u]==p1[v]（这样保证p1[]p2[]奇偶性不同），这样p2[v]=p2[u]+1。然后将 v 压入队列。

这样，4 号、5 号节点的p2[]值均为 4。

若下一个节点的p1[]、p2[]值都求出来了，就不压入队列。

直到队列中没有任何节点，bfs 结束。

以下是 bfs 代码：

void bfs(int a)
{
	q.push(a);p1[a]=0;
	while(!q.empty())
	{
		int now=q.front();q.pop();
		for(int i=head[now];i;i=e[i].nxt)
		{
			int to=e[i].end;
			if(p1[to]==-1&&p2[to]==-1)
				p1[to]=p1[now]+1,q.push(to);
			else if(p1[to]!=-1&&p2[to]==-1)
			{
				if(p1[now]%2==p1[to]%2&&p1[now]!=-1)
					p2[to]=p1[now]+1;
				else if(p2[now]%2==p1[to]%2&&p2[now]!=-1)
					p2[to]=p2[now]+1;
				else
					continue;
				q.push(to);
			}
			else
				continue;
		}
	}
	return;
}

至此，问题就很明了了：

询问 2 号工人要生产等级为 6 的零件，1 号是否提供原材料。

符合第三种情况：

$l \ge \max(p_1,p_2)$ ：可以实现 1 与旁边的任意一个节点轮换生产，最终轮到 1 生产原材料。Yes。

输出Yes。

以下是判断代码：

for(int i=1;i<=T;i++)
{
	scanf("%d%d",&a,&b);
	if(p1[a]%2==b%2&&p1[a]!=-1&&p1[a]<=b)
		printf("Yes\n");
	else if(p2[a]%2==b%2&&p2[a]!=-1&&p2[a]<=b)
		printf("Yes\n");
	else
		printf("No\n");
}