深度 $dep$。

深度最大的公共祖先。

1. 先把 $x$ 的祖先进行标记，再让 $y$ 一路往上遍历祖先，第一个碰到的被 $x$ 标记过得祖先即为最近公共祖先，复杂度 $O(n)$。

int LCA(int x, int y) {
	memset(vis, 0, sizeof(vis));
	while (x != 0) {
		vis[x] = 1;
		x = fa[x];
	}
	while (vis[y] == 0) {
		y = fa[y];
	}
	return y;
}

2. 两个点同时走，移动到一个深度，然后同时往上走，直到碰到的时候，就找到了。

void dfs(int u) {//深度
	dep[u] = dep[fa[u]] + 1;
	for (int i = head[u]; i != -1; i = E[i].next) {//链式前向星
		int v = E[i].v;
		if (v != fa[u]) {
			fa[v] = u;
			dfs(v);
		}
	}
}

int LCA(int x, int y) {
	if (dep[x] < dep[y]) {
		swap(x, y);
	}
	while (dep[x] > dep[y]) {
		x = fa[x];
	}
	while (x != y) {
		x = fa[x];
		y = fa[y];
	}
	return x;
}

3. 以二进制的方式往上跳。

求出 $2^K \le dep[x]$。

int K = 0;
while ((1 << (K + 1)) <= dep[x]) {
	K++;
}
for (int i = K; i >= 0; i--) {
	//如果 x 的 2 ^ i 的祖先深度 >= dep[y]，那么就让 x 跳到 2 ^ i 这个祖先的位置。
	
}

设 $len = dep[x] - dep[y]$，那么 $len$ 的二进制下中的 $1$ 的位置就表示 $x$ 要跳 $2^i$ 步，因为方案是唯一的，所以从大到小凑，一定不会错。

如果 $dep[x] + 2^i \ge dep[y]$，那么 $2^i$ 这一步是必须跳的。

如果这一步不跳，那就永远不能跳到 $dep[y]$。

$2^i > 2^{i - 1} + 2^{i - 2} + \dots + 2^0$。

任意整数都可以被表示成多个不同的二进制幂次数字之和。

表示方式是唯一的。

1. 状态：$fa[i][j]$ 表示 $i$ 的距离为 $2^j$ 的祖先是谁。
2. 状态转移方程：$fa[i][j] = fa[fa[i][j - 1]][j - 1]$。

$i$ 的 $2^j$ 的祖先其实就是 $i$ 的 $2^{j - 1}$ 祖先的 $2^{j - 1}$。

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


typedef long long ll;
int n, q, F;
int d[600005];
int fa[600005][25];

int head[600005];
struct Node {
    int v, nex;
} e[12000005]; 
int ecnt;
void add(int u, int v) {
    ecnt++;
    e[ecnt].v = v;
    e[ecnt].nex = head[u];
    head[u] = ecnt;
}

void dfs(int father, int root) {
    d[root] = d[father] + 1;
    fa[root][0] = father;
    for (int i = 1; i <= 19; i++) {
        fa[root][i] = fa[fa[root][i - 1]][i - 1];
    }
    for (int i = head[root]; i != 0; i = e[i].nex) {
        int v = e[i].v;
        if (v != father) {
            dfs(root, v);
        }
    }
    return;
}

int LCA(int x, int y) {
    if (d[x] < d[y]) { 
        swap(x, y);
    }
    for (int i = 19; i >= 0; i--) {
        if (d[fa[x][i]] >= d[y]) {
            x = fa[x][i];
        }
    }
    if (x == y) {
        return x;
    }
    for (int i = 19; i >= 0; i--) {
        if (fa[x][i] != fa[y][i]) {
            x = fa[x][i];
            y = fa[y][i];
        }
    }
    return fa[x][0];
}

int main() {
    cin >> n >> q;
    for (int i = 1; i < n; i++) {
        int a, b;
        cin >> a >> b;
        add(a, b);
        add(b, a);
    }
    dfs(0, 1);
    while (q--) {
        int a, b;
        cin >> a >> b;
        cout << LCA(a, b) << "\n";
    }
    return 0;
}