自己也不知道是什么写法的lca（得30pts）

#include<bits/stdc++.h>
using namespace std;
const int M = 500010;
int n, m, s, fa[22][M], dep[M];
vector<int> v[M];
void dfs(int x, int pre) {
	fa[0][x] = pre, dep[x] = dep[pre] + 1;
	for (int i = 0; i < v[x].size(); i++) {
		int y = v[x][i];
		if (y != pre) dfs(y, x);
	}
}
void Up(int &x, int step) {
	for (int i = 21; i >= 0; i--) {
		if (step & (1 << i)) x = fa[i][x];
	}
}
int LCA(int x, int y) {
	if (dep[x] < dep[y]) swap(x, y);
	Up(x, dep[x]-dep[y]);
	if (x == y) return x;
	for (int i = 21; i >= 0; i--) {
		if (fa[i][x] != fa[i][y])
			x = fa[i][x], y = fa[i][x];
	}
	return fa[0][x];
}
int main() {
	scanf("%d%d%d", &n, &m, &s);
	for (int i = 2; 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 i = 1; i < 22; i++)
		for (int j = 1; j <= n; j++)
			fa[i][j] = fa[i - 1][fa[i - 1][j]];
	while(m--) {
		int a, b; scanf("%d%d", &a, &b);
		printf("%d\n", LCA(a, b));
	}
	return 0;
}