C++14(g++5.4) 解法, 执行用时: 698ms, 内存消耗: 25236K, 提交时间: 2019-09-07 15:32:49

#include <bits/stdc++.h>
using namespace std;
const int M = 1e5+10;
int f[M][30];
vector <int > a[M];
int  d[M];
int dis[M];
void dfs(int x,int y){
     f[x][0]=y;
     d[x]=d[y]+1;
    for(int i=1;i<20;i++){
        f[x][i]=f[f[x][i-1]][i-1];
    }
    for(int i=0;i<a[x].size();i++){
        if(a[x][i]!=y){
            dis[a[x][i]]=dis[x]+1;
            dfs(a[x][i],x);
        }
    }
}
int lca(int x,int y){
    if(d[x]<d[y]){
    swap(x,y);
    }
    int dd=d[x]-d[y];
    for(int i=0;i<20;i++){
        if(dd >>i &1){
            x=f[x][i];
        }
    }
    if(x==y){
    return x;
    }
    for(int i=20-1;i>=0;i--){
        if(f[x][i]!=f[y][i]){
        x=f[x][i];
        y=f[y][i];
        }
    }
    return f[x][0];
}
int n,q;int x,y;
int main(){
    cin>>n;
    for(int i=1;i<n;i++){
        cin>>x>>y;
        a[x].push_back(y);
        a[y].push_back(x);
    }
    dfs(1,0);
    cin>>q;
    for(int i=1;i<=q;i++){
        cin>>x>>y;
        int haha=lca(x,y);
        cout<<dis[x]+dis[y]-dis[haha]*2<<endl;
    }
}

C++(g++ 7.5.0) 解法, 执行用时: 368ms, 内存消耗: 21588K, 提交时间: 2022-10-17 23:17:34

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;

vector<int> e[N];
int dep[N], fa[N][20];
void dfs(int u, int father) {
    dep[u] = dep[father] + 1;
    fa[u][0] = father;
    for(int i = 1; i <= 19; i ++) fa[u][i] = fa[fa[u][i-1]][i-1];
    for(int v : e[u]) {
        if(v != father)  dfs(v, u);
    }
}
int lca(int u, int v) {
    if(dep[u] < dep[v]) swap(u, v);
    for(int i = 19; i >= 0; i --) {
        if(dep[fa[u][i]] >= dep[v]) u = fa[u][i];
    }
    if(u == v) return v;
    for(int i = 19; i >= 0; i --) {
        if(fa[u][i] != fa[v][i]) u = fa[u][i], v = fa[v][i];
    }
    return fa[u][0];
}
int main () {
    int n, m;
    cin >> n;
    for(int u, v, i = 0; i < n-1; i ++) {
        cin >> u >> v;
        e[u].push_back(v); e[v].push_back(u);
    }
    dfs(1, 0);
    cin >> m;
    for(int i = 0, u, v; i < m; i ++) {
        cin >> u >> v;
        int _lca = lca(u, v);
        cout << dep[u] - dep[_lca] * 2 + dep[v] << endl;
    }
    
    return 0;
}

C++ 解法, 执行用时: 332ms, 内存消耗: 18172K, 提交时间: 2022-02-06 11:34:44

#include<bits/stdc++.h>
using namespace std;
int d[100001],f[100001][17];
vector <int> g[100001];
void init(int x){
	d[x] = d[f[x][0]] + 1;
	int i;
	for (i = 0;i < 16;i++)
		f[x][i + 1] = f[f[x][i]][i];
	for (i = 0;i < g[x].size();i++)
		if (g[x][i] != f[x][0]){
			f[g[x][i]][0] = x;
			init(g[x][i]);
		}
}
int lca(int x,int y){
	if (d[x] < d[y])
		swap(x,y);
	int ans = 0,i;
	for (i = 16;i >= 0;i--)
		if (d[f[x][i]] >= d[y]){
			x = f[x][i];
			ans += 1 << i;
		}
	if (x == y)
		return ans;
	for (i = 16;i >= 0;i--)
		if (f[x][i] != f[y][i]){
			x = f[x][i];
			y = f[y][i];
			ans += 2 << i;
		}
	return ans + 2;
}
int main(){
	int n,q,x,y,i;
	cin>>n;
	for (i = 1;i < n;i++){
		cin>>x>>y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	init(1);
	cin>>q;
	while (q--){
		cin>>x>>y;
		cout<<lca(x,y)<<endl;
	}
	return 0;
}