LCA

朴素作法

对于每次询问，分别从两点出发，遍历所有祖先节点找到相同的节点

树上倍增

利用倍增思想，一次可以走2^k

首先预处理depth[N]数组，表示每个点的深度，预处理fa[N][M]数组，fa[a][i]表示a点向上走2ⁱ步后到达的节点(bfs)

假设查询的点为x,y，且x深度大于y

预处理数组

1.从x出发，利用fa[x][i]数组，找到与y同一层的x的祖宗节点z，若此时z==y，则已经找到，最近公共祖先为y

2.否则从z和y出发，利用f[N][M]寻找z和y的最近公共祖先(M从log(max(depth))遍历到0)

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int N = 40007, M = 2*N;

int fa[N][17], depth[N], q[N];
int h[N], e[M], ne[M], idx;

void add(int a, int b) {
	e[idx] = b, ne[idx] = h[a], h[a] = idx++;
} 

void bfs(int root) {
	memset(depth, 0x3f, sizeof depth);
	depth[0] = 0;
	depth[root] = 1;
	int hh = 0, tt = 0;
	q[0] = root;
	while(hh <= tt) {
		int x = q[hh++];
		for (int i = h[x]; i != -1; i = ne[i]) {
			int b = e[i];
			if (depth[b] > depth[x] + 1) {
				depth[b] = depth[x] + 1;
				fa[b][0] = x;
				for (int i = 1; i <= 15; i++) {
					fa[b][i] = fa[fa[b][i-1]][i-1];
				}
				q[++tt] = b;
			}
		}
	}
}

int lca(int a, int b){
	if (depth[a] < depth[b]) {
		swap(a, b);
	}
	
	for (int i = 15; i >= 0; i--) {
		if (depth[fa[a][i]] >= depth[b]) {
			a = fa[a][i];
		}
	}
	if (a == b) return a;
	
	for (int i = 15; i >= 0; i--) {
		if (fa[a][i] != fa[b][i]) {
			a = fa[a][i];
			b = fa[b][i];
		}
	}
	return fa[a][0];
}

int main(){
	memset(h, -1, sizeof h);
	int n,m;
	cin >> n;
	int root;
	for (int i = 0; i < n; i++) {
		int a, b;
		cin >> a >> b;
		if (b == -1) {
			root = a;
		} else {
			add(a,b);
			add(b,a);
		}
	}
	
	bfs(root);
	
	cin >> m;
	for (int i = 0; i < m; i++) {
		int x, y;
		cin >> x >> y;
		int ans = lca(x, y);
		if (ans == x) {
			cout << 1 << endl;
		} else if (ans == y) {
				cout << 2 << endl;
		} else {
			cout << 0 << endl;
		}
	}
	return 0;
}

Tarjan

将树中的点分成三类，一类是已经搜索并且回溯过的(2)，一类是正在搜索中的(1)，一类是未搜索的(0)，在dfs搜索某个点时将该点标记为1，对该点的子节点使用tarjan，然后利用并查集维护子节点的父节点为该节点。

对子节点应用完tarjan后将遍历所有对该点的询问，若询问的另一点st为2，则已经搜索并回溯过，利用并查集find到祖宗节点，该节点便是该点与另一点的最近公共祖先

int main()
{
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    for (int i = 0; i < n - 1; i ++ )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c), add(b, a, c);
    }

    for (int i = 0; i < m; i ++ )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        if (a != b)
        {
            query[a].push_back({b, i});
            query[b].push_back({a, i});
        }
    }

    for (int i = 1; i <= n; i ++ ) p[i] = i;

    dfs(1, -1);
    tarjan(1);

    for (int i = 0; i < m; i ++ ) printf("%d\n", res[i]);

    return 0;
}