C++(g++ 7.5.0) 解法, 执行用时: 1790ms, 内存消耗: 50188K, 提交时间: 2023-04-17 17:05:52

#include<iostream>
#include<vector>
#include<algorithm>
#define endl '\n'
using namespace std;
const int N=5e5+10,M=20;
vector<int> e[N],dep(N);
int n,m;
int x,y;
int f[N][M];
void dfs(int u,int fa){
    dep[u]=dep[fa]+1;
    f[u][0]=fa;
    for(int i=1;i<=19;i++)
        f[u][i]=f[f[u][i-1]][i-1];

    for(auto &x:e[u])
        if(x!=fa)dfs(x,u);
}
inline int lca(int a,int b){
    if(dep[a]<dep[b])swap(a,b);
    for(int i=19;i>=0;i--)if(dep[f[a][i]]>=dep[b])a=f[a][i];
    if(a==b)return a;
    for(int i=19;i>=0;i--)
        if(f[a][i]!=f[b][i])
            a=f[a][i],b=f[b][i];
    return f[a][0];
}
inline int dis(int a,int b){
    return dep[a]+dep[b]-2*dep[lca(a,b)];
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    cin>>n;
    int a,b;
    for(int i=1;i<n;i++){
        cin>>a>>b;
        e[a].push_back(b);
        e[b].push_back(a);
    }
    dfs(1,0);
    cin>>x>>y;
    cin>>m;
    for(int i=1;i<=m;i++){
        cin>>a>>b;
        cout<<min(dis(a,b),min(dis(a,x)+dis(b,y),dis(a,y)+dis(b,x)))<<endl;
    }
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 1876ms, 内存消耗: 50560K, 提交时间: 2019-05-23 21:36:06

#include<bits/stdc++.h>
using namespace std;
#define maxn 1000005
int n,m,q,i,j,k,s,t,h[maxn],ne[maxn],p[maxn],d[maxn],f[maxn][20];
int LCA(int x,int y){
	int i;
	if(d[x]>d[y]) swap(x,y);
	if(d[x]!=d[y]) for(i=19;~i;i--) if(d[y]-d[x]>>i&1) y=f[y][i];
	if(x!=y){
		for(i=19;~i;i--)
		{
			if(f[x][i]!=f[y][i])
			{
				x=f[x][i];
				y=f[y][i];
			}
		}
		x=f[x][0];
	}
	return x;
}
int dis(int x,int y){
	return d[x]+d[y]-(d[LCA(x,y)]<<1);
}
void dfs(int x){
	for(int i=1;i<20;i++) f[x][i]=f[f[x][i-1]][i-1];
	for(int i=h[x];i;i=ne[i]) if(p[i]!=f[x][0])
	{
		f[p[i]][0]=x;
		d[p[i]]=d[x]+1;
		dfs(p[i]);
	}
}
int main(){
	scanf("%d",&n);
	for(i=1;i<n;i++){
		scanf("%d%d",&j,&k);
		p[++m]=k;
		ne[m]=h[j];
		h[j]=m;
		p[++m]=j;
		ne[m]=h[k];
		h[k]=m;
	}
	dfs(1);
	scanf("%d%d%d",&s,&t,&q);
	while(q--){
		scanf("%d%d",&i,&j);
		printf("%d\n",min(dis(i,j),min(dis(i,s)+dis(j,t),dis(i,t)+dis(j,s))));
	}
	return 0;
}