求助LCA板子（玄关

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>

using namespace std;

const int N = 2e5 + 10, M = 2 * N;

int n, m;
int rt;
int p[N][35];
int h[N], e[M], ne[M], idx, d[N], fa[N];

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

inline void dfs(int x, int de)
{
	d[x] = de;
	for (int i = h[x]; i != -1; i = ne[i])
	{
		int j = e[i];
//		if (e[i] == fa[x]) continue;
		dfs(j, de + 1);
	}
}

inline void init()
{
	memset(p, -1, sizeof p);   
	for (int i = 1; i <= n; i ++ ) p[i][0] = fa[i];
	for (int j = 1; (1 << j) <= n; j ++ )
	  for (int i = 1; i <= n; i ++ )
	    if (p[i][j - 1] != -1)
	      p[i][j] = p[p[i][j - 1]][j - 1];
}

inline int lca(int a, int b)
{
	int k = (int)(log2(d[a]));
	for (int i = k; i >= 0; i -- )
	  if (d[a] - (1 << i) >= d[b])
	    a = p[a][i];
	if (a == b) return a;
	for (int i = k; i >= 0; i -- )
	  if (p[a][i - 1] != -1 && p[a][i] != p[b][i]) a = p[a][i], b = p[b][i];
	return p[a][0];
}

int main()
{
//	memset(fa, -1, sizeof fa);
	memset(h, -1, sizeof h);
	scanf("%d%d", &n, &m);
	int nc = n - 1, x, y;
	while (nc -- )
	{
		scanf("%d%d", &x, &y);
		add(x, y);
//		add(y, x);
		fa[y] = x; 
	}
	rt = 1;
	while (fa[rt] != 0) rt = fa[rt];	
/*	for (int i = 1; i <= n; i ++ )
		if (fa[i] == 0)
		{
			rt = i;
			break;
		}*/
	dfs(rt, 1);
//	for (int i = 1 ; i <= n; i ++ ) cout << d[i] << '\n';
	init();
	while (m -- )
	{
		scanf("%d%d", &x, &y);
		if (d[x] < d[y]) swap(x, y); 
		printf("%d\n", lca(x, y));
	}
	return 0;
}