C++14(g++5.4) 解法, 执行用时: 509ms, 内存消耗: 2012K, 提交时间: 2020-05-03 15:43:28

#include<bits/stdc++.h>
#define IO ios::sync_with_stdio(false), cin.tie(0)
#define INF 0x3f3f3f3f
typedef long long ll;
using namespace std;
int n,m;
int f[100005];
int dep[100005];
int dfs(int x){
	if(dep[x]!=0||f[x]==0)return dep[x];
	else return dep[x]=dfs(f[x])+1;
}
void init(){
	cin>>n>>m;
	int fa,s;
	memset(f,0,sizeof(f));
	memset(dep,0,sizeof(dep));
	for(int i=1;i<n;i++){
		cin>>fa>>s;
		f[s]=fa;
	}
	for(int i=1;i<=n;i++){
		if(f[i]&&dep[i]==0){
			dfs(i);
		}
	}
//	cout<<"---"<<endl;
//	for(int i=1;i<=n;i++){
//		cout<<i<<" "<<dep[i]<<endl;
//	}
}
int lca(int ta,int tb){
	while(dep[ta]!=dep[tb]){
		if(dep[ta]>dep[tb]){
			ta=f[ta];
		}else{
			tb=f[tb];
		}
	}
	while(ta!=tb){
		ta=f[ta];
		tb=f[tb];
	}
	return ta;
}
int main()
{
	IO;
	init();
	for(int i=0;i<m;i++){
		int ta,tb;
		cin>>ta>>tb;
		int tmp=lca(ta,tb);
		//cout<<"tmp="<<tmp<<endl; 
		int dis=dep[ta]+dep[tb]-2*dep[tmp];
		if(dis<=4||ta==tmp||tb==tmp){
			cout<<"NO"<<endl<<dis<<endl;
		}else{
			cout<<"YES"<<endl<<dis<<endl;
		}
	}
 	return 0;
}
/*


*/ 

C++ 解法, 执行用时: 747ms, 内存消耗: 7656K, 提交时间: 2022-04-12 20:26:46

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,q,v[100005],d[100005],f[100005];
vector<ll>m[100005];
void build(ll now,ll de){
	v[now]=1;
	d[now]=de;
	ll l=m[now].size();
	for(int i=0;i<l;i++){
		ll to=m[now][i];
		if(!v[to]){
			build(to,de+1);
		}
	}
}
int main() {
	cin>>n>>q;
	ll x,y;
	for(int i=1;i<n;i++){
		cin>>x>>y;
		f[y]=x;
		m[x].push_back(y);
	}
	x=1;
	while(f[x])x=f[x];
	build(x,1);
	while(q--){
		cin>>x>>y;
		ll ans=0,flag=1;
		while(d[x]>d[y]){
			x=f[x];
			ans++;
		}
		while(d[y]>d[x]){
			y=f[y];
			ans++;
		}
		if(x==y){
			flag=0;
		}else{
			while(x!=y){
				x=f[x];
				y=f[y];
				ans+=2;
			}
			if(ans<=4)flag=0;
		}
		cout<<(flag==1?"YES":"NO")<<endl<<ans<<endl;
	}
	return 0;
}