rt，按道理来说前者常数应该小于倍增算法。

树剖：

/*
树链剖分求 LCA 
*/

#include <bits/stdc++.h>
#define int long long
#define ls p << 1
#define rs p << 1 | 1

using namespace std;

const int N = 5e5 + 5;

int n, m, root, P = 1e18, _index;

int a[N], f[N], h[N], siz[N], t[N], dfn[N], rdfn[N], d[N], tree[N << 2], change[N << 2];

vector <int> v[N];

void orz (int p) {
	tree[p] %= P;
	change[p] %= P;
}

void pushup (int p) {
	tree[p] = tree[ls] + tree[rs];
	orz (p);
}

void pushdown (int len, int p) {
	change[ls] += change[p];
	change[rs] += change[p];
	tree[ls] += change[p] * (len - (len >> 1));
	tree[rs] += change[p] * (len >> 1);
	change[p] = 0;
	orz (p);
	orz (ls);
	orz (rs);
}

void build (int l = 1, int r = n, int p = 1) {
	if (l == r) {
		tree[p] = a[rdfn[l]];
	} else {
		int mid = (l + r) >> 1;
		build (l, mid, ls);
		build (mid + 1, r, rs);
		pushup (p);
	}
}

void update (int l, int r, int k, int cl = 1, int cr = n, int p = 1) {
	if (l > r) { swap (l, r); }
	if (cl > r || cr < l) {
		return;
	} else if (cl >= l && cr <= r) {
		tree[p] += k * (cr - cl + 1);
		change[p] += k;
        orz (p);
	} else {
		int mid = (cl + cr) >> 1;
		pushdown (cr - cl + 1, p);
		update (l, r, k, cl, mid, ls);
		update (l, r, k, mid + 1, cr, rs);
		pushup (p);
	}
}

int query (int l, int r, int cl = 1, int cr = n, int p = 1) {
	if (l > r) { swap (l, r); }
	if (cl > r || cr < l) {
		return 0;
	} else if (cl >= l && cr <= r) {
		return tree[p];
	} else {
		int mid = (cl + cr) >> 1;
		pushdown (cr - cl + 1, p);
		return (query (l, r, cl, mid, ls) + query (l, r, mid + 1, cr, rs)) % P;
	}
}

void dfs1 (int cur, int father) {
	f[cur] = father;
	siz[cur] = 1;
	d[cur] = d[father] + 1;
	
	for (int i = 0; i < v[cur].size (); ++ i) {
		if (v[cur][i] != father) {
			dfs1 (v[cur][i], cur);
			siz[cur] += siz[v[cur][i]];
			
			if (siz[v[cur][i]] > siz[h[cur]]) { h[cur] = v[cur][i]; }
		}
	}
}

void dfs2 (int cur, int top) {
	dfn[cur] = ++ _index;
	rdfn[_index] = cur;
	t[cur] = top;
	
	if (h[cur]) {
		dfs2 (h[cur], top);
		
		for (int i = 0; i < v[cur].size (); ++ i) {
			if (v[cur][i] != f[cur] && v[cur][i] != h[cur]) {
				dfs2 (v[cur][i], v[cur][i]);
			}
		}
	}
}

int LCA (int x, int y) {
	while (t[x] != t[y]) {
		if (d[t[x]] < d[t[y]]) { swap (x, y); }
		
		x = f[t[x]];
	}
	
	return d[x] < d[y] ? x : y;
}

signed main () {
	cin >> n >> m >> root;
	
	for (int x, y, i = 1; i < n; ++ i) {
		cin >> x >> y;
		v[x].push_back (y);
		v[y].push_back (x);
	}
	
	dfs1 (root, 0);
	
	dfs2 (root, root);
	
	for (int x, y; m; -- m) {
		cin >> x >> y;
		cout << LCA (x, y) << '\n';
	}
	
	return 0; 
}

倍增：

#include <bits/stdc++.h>

using namespace std;

const int N = 5e5 + 5, LOG = 25;

int n, m, s;
int f[N][LOG];
int d[N];
vector <int> v[N];

int LCA (int x, int y) {
	
	if (x == y) { // 特判 
		return x;
	}
	
	// 找到深度大的结点
	
	if (d[x] < d[y]) {
		swap (x, y);
	}
	
	// 第一阶段，让 x 往上跳
	
	int dep = d[x] - d[y];
	
	for (int k = 20; k >= 0; -- k) {
		if (dep >= (1 << k)) {
			dep -= (1 << k);
			x = f[x][k];
		}
	}
	
	if (x == y) { // 特判 x=y 的时候，直接返回 
		return x;
	}
	
	// 第二阶段，让 x,y 一起跳
	
	for (int k = 20; k >= 0; -- k) {
		if (f[x][k] != f[y][k]) {
			x = f[x][k];
			y = f[y][k];
		}
	}
	
	// 返回父亲
	
	return f[x][0];
}

void dfs (int cur, int father) {
	f[cur][0] = father;
	d[cur] = d[father] + 1;
	for (int i = 0; i < v[cur].size (); ++ i) {
		if (v[cur].at (i) != father) {
			dfs (v[cur].at (i), cur);
		}
	}
}

int main () {
	scanf ("%d %d %d", &n, &m, &s);
	
	for (int i = 1; i < n; ++ i) {
		int x, y;
		scanf ("%d %d", &x, &y);
		v[x].push_back (y);
		v[y].push_back (x);
	}
	
	dfs (s, 0);
	
	for (int j = 1; j <= 20; ++ j) {
		for (int i = 1; i <= n; ++ i) {
			f[i][j] = f[f[i][j - 1]][j - 1];
		}
	}
	
	while (m --) {
		int x, y;
		scanf ("%d %d", &x, &y);
		printf ("%d \n", LCA (x, y));
	}
	
	return 0;
}