$rt$

在用 $lg$ 数组优化的过程中，如下写：

//#pragma GCC optimize (2)
#include <bits/stdc++.h>
#define int long long

using namespace std;
const int N = 5e5 + 5;
const int M = 1e6 + 5; 

int n, m, s, cnt;
int head[N];
struct node {
	int u, v;
	int nxt;
};
node a[M];
int lg[N], depth[N], f[N][25];

void add (int x, int y) {
	a[ ++ cnt].nxt = head[x];
	a[cnt].u = x;
	a[cnt].v = y;
	head[x] = cnt;
}

void dfs (int pnt, int fa) {
	f[pnt][0] = fa, depth[pnt] = depth[fa] + 1;
	for (int i = 1; i <= lg[depth[pnt]]; i ++ )
		f[pnt][i] = f[f[pnt][i - 1]][i - 1];
	for (int i = head[pnt]; i; i = a[i].nxt)
		if (a[i].v != fa)	dfs (a[i].v, pnt);
}

int LCA (int x, int y) {
	if (depth[x] < depth[y])
		swap (x, y);
	while (depth[x] > depth[y])
		x = f[x][lg[depth[x] - depth[y]] - 1];
	if (x == y)
		return x;
	for (int i = lg[depth[x]] - 1; i >= 0; i -- )
		if (f[x][i] != f[y][i])
			x = f[x][i], y = f[y][i];
	
	return f[x][0];
}

signed main () {
	scanf ("%lld%lld%lld", &n, &m, &s);
	for (int i = 1; i < n; i ++ ) {
		int u, v;
		scanf ("%lld%lld", &u, &v);
		add (u, v), add (v, u);
	}
	
	for (int i = 1; i <= n; i ++ )
		lg[i] = lg[i - 1] + ((1 << lg[i - 1]) == i);
	
	dfs (s, 0);
	
	while (m -- ) {
		int x, y;
		scanf ("%lld%lld", &x, &y);
		printf ("%lld\n", LCA (x, y));
	}
	
	return 0;
}

就过了

但将 $56$ 行的末尾减 $1$ ，其余用到 $lg$ 数组的部分进行相应的更改，具体来说：

1. $27$ 行 lg[depth[pnt]] 改为 lg[depth[pnt]] + 1

2. $37,40$ 行的 $lg$ 数组减一

就直接：评测记录

所以有人帮忙解答一下吗qwq，悬赏1关注qwq