P3379 #345 AC 别的TLE

#include <iostream>
#include <cstdio>
#include <vector>
const int N = 5e5 + 7;
const int J = 30;
std::vector <int> e[N];
int n, m, s;
int fa[J][N], dep[N], logn[N];
inline void add(int x, int y) {
	e[x].push_back(y);
	e[y].push_back(x);
}
void init(int u, int f) {
	dep[u] = dep[f] + 1;
	fa[0][u] = f;
	for(int i = 1; i <= logn[dep[u]]; i++)
		fa[i][u] = fa[i - 1][fa[i - 1][u]];
	for(auto i : e[u]) 
		if(i ^ f) init(i, u);
}
int LCA(int x, int y) {
	if(dep[x] > dep[y]) std::swap(x, y);
	for(int i = logn[dep[y]]; i >= 0; i--)
		if(dep[fa[i][y]] >= dep[x]) 
			y = fa[i][y];
	for(int i = logn[dep[y]]; i >= 0; i--)
		if(fa[i][x] != fa[i][y]) 
			x = fa[i][x], y = fa[i][y];
	return x == y ? x : fa[0][x];
}
int main() {
	std::cin >> n >> m >> s;
	int v, u;
	for(int i = 0; i < n - 1; i++) {
		std::cin >> u >> v;
		add(u, v);
		add(v, u);
	}
	logn[1] = 0;
	for(int i = 2; i <= n; i++)
		logn[i] = logn[i / 2] + 1;
	init(s, 0);
	int a, b;
	for(int i = 0; i < m; i++) {
		std::cin >> a >> b;
		std::cout << LCA(a, b) << '\n';
	}
	return 0;
}