C++(g++ 7.5.0) 解法, 执行用时: 43ms, 内存消耗: 7852K, 提交时间: 2023-03-23 20:09:09

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int n, m, dep[40010], fa[40010][20];
vector<int> G[40010];
void dfs(int u, int f) {
    dep[u] = dep[f] + 1;
    fa[u][0] = f;
    for (int i = 1; (1 << i) < dep[u]; i++) {
        fa[u][i] = fa[fa[u][i - 1]][i - 1];
    }
    for (auto v : G[u]) {
        if (v != f) {
            dfs(v, u);
        }
    }
}
int lca(int x, int y) {
    if (dep[x] > dep[y]) {
        swap(x, y);
    }
    for (int i = 19; i >= 0; i--) {
        if (dep[x] <= dep[y] - (1 << i)) {
            y = fa[y][i];
        }
    }
    if (x == y) {
        return x;
    }
    for (int i = 19; i >= 0; i--) {
        if (fa[x][i] != fa[y][i]) {
            x = fa[x][i];
            y = fa[y][i];
        }
    }
    return fa[x][0];
}
int main() {
    scanf("%d", &n);
    int root = 0;
    for (int i = 0; i < n; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        if (y == -1) {
            root = x;
        } else {
            G[x].push_back(y);
            G[y].push_back(x);
        }
    }
    dfs(root, 0);
    scanf("%d", &m);
    while (m--) {
        int a, b;
        scanf("%d%d", &a, &b);
        int p = lca(a, b);
        if (p == a) {
            puts("1");
        } else if (p == b) {
            puts("2");
        } else {
            puts("0");
        }
    }
    return 0;
}

C++14(g++5.4) 解法, 执行用时: 189ms, 内存消耗: 7904K, 提交时间: 2020-01-21 11:48:43

#include <bits/stdc++.h>
using namespace std;


const int MAXN = 4e4+1;
int N, M;

vector<int> G[MAXN];
int H[MAXN];
int F[MAXN][20];

void dfs(int s, int f) {
  // cout << "dfs " << s << " " << f << endl;
  F[s][0] = f, H[s] = H[f]+1;
  for (int i = 0; i < 19; i++) F[s][i+1] = F[F[s][i]][i];
  for (auto t: G[s]) if (t != f) dfs(t, s);
}
int lca(int x, int y) {
  if (H[x] < H[y]) swap(x, y);
  for (int i = 19; i >= 0; i--) if (H[F[x][i]] >= H[y]) x = F[x][i];
  if (x == y) return x;
  for (int i = 19; i >= 0; i--) if (F[x][i] != F[y][i]) x = F[x][i], y = F[y][i];
  return F[x][0];
}

int main() {
  cin >> N;
  int root = 0;
  for (int i = 0; i < N; i++) {
    int a, b; cin >> a >> b;
    if (b == -1) root = a;
    else G[b].push_back(a), G[a].push_back(b);
  }
  dfs(root, 0);
  cin >> M;
  while (M--) {
    int x, y; cin >> x >> y;
    int z = lca(x, y);
    // cout << x << " " << y << ":" << z << endl;
    if (z == x) cout << 1 << endl;
    else if (z == y) cout << 2 << endl;
    else cout << 0 << endl;
  }
}

C++ 解法, 执行用时: 183ms, 内存消耗: 6660K, 提交时间: 2022-02-06 12:07:51

#include<bits/stdc++.h>
using namespace std;
int d[40001],f[40001][16];
vector <int> g[40001];
void init(const int &x){
	d[x] = d[f[x][0]] + 1;
	int i;
	for (i = 0;i < 15;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){
	int t = 2;
	if (d[x] < d[y]){
		swap(x,y);
		t = 1;
	}
	for (int i = 15;i >= 0;i--)
		if (d[f[x][i]] >= d[y])
			x = f[x][i];
	if (x == y)
		return t;
	return 0;
}
int main(){
	int n,m,a,b,root;
	cin>>n;
	while (n--){
		cin>>a>>b;
		if (b == -1)
			root = a;
		else{
			g[a].push_back(b);
			g[b].push_back(a);
		}
	}
	init(root);
	cin>>m;
	while (m--){
		cin>>a>>b;
		cout<<lca(a,b)<<endl;
	}
	return 0;
}