来点不一样的，用树链剖分求LCA。 先把树剖成链，记录每个点$u$所在链的最顶端节点 $top_u$， 每次往上跳即可。

#include <bits/stdc++.h>
using namespace std;

/***********************

Author : ACgod
Date : 2022/5/21
School : Xiamen No.1 High School of Fujian

***********************/

#define reg register
#define rep(i, a, b) for(register int i = a; i <= b; i ++)
#define pb push_back

vector<int> e[500005];
int n, q;

template <class T> T read() {
  reg T s=0,f=1; reg char ch = getchar();
  while(ch<'0'||ch>'9')ch=getchar();
  while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+ch-'0',ch=getchar();
  return f*s;
}

int maxson[500005], size[500005];
int top[500005], dep[500005];
int fat[500005];

void dfs1(int u, int fa) {
  dep[u] = dep[fa] + 1;
  fat[u] = fa;
  int sizeofson = 0;
  for(int i = 0; i < e[u].size(); i ++) {
    int to = e[u][i];
    if(to == fa) continue;
    dfs1(to, u);
    size[u] += size[to];
    if(size[to] > sizeofson) {
      maxson[u] = to;
      sizeofson = size[to];
    }
  }
  size[u]++;
}

void dfs2(int u, int topf, int fa) {
  top[u] = topf;
  for(int i = 0; i < e[u].size(); i ++) {
    int to = e[u][i];
    if(to == fa) continue;
    if(maxson[u] == to) {
      dfs2(to, topf, u);
    }
    else dfs2(to, to, u);
  }
}

int lca(int x, int y) {
  if(dep[top[x]] < dep[top[y]]) swap(x, y);
  return top[x] == top[y] ? (dep[x] < dep[y] ? x : y ): lca(fat[top[x]], y);
}

int main() {
  n = read<int>(), q = read<int>();
  rep(i, 1, n - 1) {
    int u, v;
    u = read<int>(), v = read<int>();
    e[u].pb(v), e[v].pb(u);
  }
  dfs1(1, 0);
  dfs2(1, 1, 0);
  rep(i, 1, q) {
    int x, y;
    x = read<int>(), y = read<int>();
    printf("%d\n", lca(x, y));
  }
  return 0;
}