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;
}