TLE求助

#include <bits/stdc++.h>
#define MAXN 500005
#define INF 2147483647
using namespace std;
int n, m, s;
int dis[MAXN][22], dep[MAXN], lg[MAXN];
struct EDGE {
	int to, next;
}edge[MAXN<<1];
int head[MAXN], cnt;
void insertedge(int u, int v) {
	cnt++;
	edge[cnt].to = v;
	edge[cnt].next = head[u];
	head[u] = cnt;
}
int dfs(int u, int fa) {
	dis[u][0] = fa;
	dep[u] = dep[fa]+1;
	for(int i = 1; i <= lg[dep[u]]; i++)
		dis[u][i] = dis[dis[u][i-1]][i-1];
	for(int i = head[u]; i; i = edge[i].next)
		if(edge[i].to != fa)
			dfs(edge[i].to, u);
}
int lca(int x, int y) {
	if(dep[x] < dep[y])
		swap(x, y);
	while(dep[x] > dep[y])
		x = dis[x][lg[dep[x]-dep[y]]-1];
	if(x == y)
		return x;
	for(int k = lg[dep[x]]-1; k >= 0; k--)
		if(dis[x][k] != dis[y][k])
			x = dis[x][k], y = dis[y][k];
	return dis[x][0];
}
int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m >> s;
	for(int i = 1; i < n; i++) {
		int u, v;
		cin >> u >> v;
		insertedge(u, v);
		insertedge(v, u);
	}
	for(int i = 1; i <= n; i++)
		lg[i] = lg[i-1]+(1<<lg[i-1]==i);
	dfs(s, 0);
	for(int i = 1; i <= m; i++) {
		int a, b;
		cin >> a >> b;
		cout << lca(a, b) << "\n";
	}
	return 0;
}