感谢大佬 Orz

/**
 * 题目名称：P8805 [蓝桥杯 2022 国 B] 机房
 * 题目链接：https://www.luogu.com.cn/problem/P8805
 * 做题时间：2024年6月8日
 * 考查内容：最近公共祖先
 * 难度评级：普及+/提高
 * 主要思路：注意建图的方式即可
 * 注意事项：
 **/
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int d[N], sum[N][31];
int anc[N][31];
int h[N], to[N], nxt[N], cnt;
int n, m, x, y;
int a[N];

void add(int u, int v) {
	to[++cnt] = v;
	nxt[cnt] = h[u];
	h[u] = cnt;
	a[u]++;
}

void DFS(int u, int fa) {
	d[u] = d[fa] + 1;
	anc[u][0] = fa;
	sum[u][0] = a[u];
	for(int j = 1; j < 31; j++) {
		anc[u][j] = anc[anc[u][j - 1]][j - 1];
		sum[u][j] = sum[anc[u][j - 1]][j - 1] + sum[u][j - 1];
	}
	for (int i = h[u]; i != -1; i = nxt[i]) {//遍历这个节点的所有出边
		int v = to[i];//储存一下边 u -> v 的终点
		if (v != fa) DFS(v, u);//搜索这个点的子节点
	}
}

int LCA(int u, int v) {
	int ans = 0;
	if (d[u] < d[v]) swap(u, v);
	for (int i = 30; i >= 0; i--) if (d[anc[u][i]] >= d[v]) ans += sum[u][i], u = anc[u][i];//先将较深的节点提高至一个高度
	if (u == v) return ans + a[u];
	for (int i = 30; i >= 0; i--) if (anc[u][i] != anc[v][i]) u = anc[u][i], v = anc[v][i], ans += sum[u][i] + sum[v][i];//将二者提升到最近公共祖先的下一层
	ans += sum[u][0] + sum[v][0] + sum[anc[u][0]][0];
	return ans;
}

int main() {
//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	memset(h, -1, sizeof h);
	cin >> n >> m;
	for (int i = 1; i <= n - 1; i++) {
		int u, v;
		cin >> u >> v;
		add(u, v), add(v, u);
	}
	DFS(1, 0);
//	cout << "延迟分别为："; 
//	for (int i = 1; i <= n; i++) cout << a[i] << " ";
//	cout << endl;
	for (int i = 1; i <= m; i++) {
		int u, v;
		cin >> u >> v;
		cout << LCA(u, v) << endl;
	}
	return 0;
}