链式前向星+Dijkstra优先队列优化（应该挺有用）

这题就是找树上两个点之间的距离，然后这距离是奇数就输出Yes，是偶数就输出No。可以用链式前向星+队列优化的Dijkstra解决，至于队列优化的Dijkstra算法时间复杂度好像是O(nlogn+m)，但是其原理我还理解的不够透彻，等以后理解透彻后再对这篇博客进行修改。 下面直接放代码：

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector> 
using namespace std;
//-----------------------------链式前向星的准备工作-----------------------------------
struct edge{
          
   
	int next;//上个以这条边为起点的边在存放边的数组中的位置（方便遍历） 
	int to;//终点 
	int w;//边权 
}dat[200005];//存放边的结构体(无向边大小要开2倍)
int cnt=1;//这是遍历存放边的数组用的，同时也记录着边的数量 
int head[200005];//head[u]表示以u为起点的第一条边（这里第一条指的是链式结构的头）在存放边的数组中的位置 ，无向边大小要开二倍 
void add(int u,int v,int w)//加边函数 
{
          
   
	dat[cnt].w=w;//存放边权 
	dat[cnt].to=v;//存放终点 
	dat[cnt].next=head[u];//当前边指向上一条同起点的边 
	head[u]=cnt++;//改变头结点为当前边（方便以后遍历） 
}
//------------------------------------------------------------------------------------
//-------------------------------Dijkstra（单调队列优化）的准备工作-----------------------------------
const int inf = 0x3f3f3f3f;
int dis[100005];
struct cmpx
{
          
   
	bool operator() (int &a,int &b) const
	{
          
   
		return dis[a]>dis[b];
	}
};//优先队列的排序方式 
//------------------------------------------------------------------------------------
void Dijkstra(int x)
{
          
   
	priority_queue<int,vector<int>,cmpx > q;
	memset(dis,0x3f,sizeof(dis));//刚开始x到各点的最短距离都不确定，全部初始化为inf 
	dis[x]=0;//自己到自己的最小距离是0 
	q.push(x);//确定最小距离的点扔进优先队列中 
	while(!q.empty())//队列不为空说明还有点没有确定最小距离，就要继续进行循环 
	{
          
   
		int u=q.top();//用队首的点松弛其它与其相邻的边？ 
		q.pop();//出列代表我准备用它松弛了其它与其相邻的边？ 
		for(int k=head[u];k!=0;k=dat[k].next)//遍历与队首相连的边 
		{
          
   
			int v=dat[k].to;
			if(dis[v]>dis[u]+dat[k].w)
			{
          
   
				dis[v]=dis[u]+dat[k].w;//能松弛就更新 
				q.push(v);//然后把被松弛的边的终点扔进优先队列中 
			}
		}
	}
}
int main()
{
          
   
	int n,a,b;
	cin>>n;
	for(int i=1;i<n;++i)
	{
          
   
		cin>>a>>b;
		add(a,b,1);
		add(b,a,1);//无向边 
	}
	cin>>a>>b;
	Dijkstra(a);
	if(dis[b]%2==1) cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
	return 0;
}