这是我之前写的用链式前向星存图的四毛子，AC了

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef unsigned long long ULL;
typedef long long LL;
typedef pair<int,int> PII;
int n,q,r;
int h[500010],w[1000010],e[1000010],ne[1000010],idx;
int d[500010],p[1000010],dfc,f[300010][23],to[300010],gt[1000010],num;
int st[2050][15][15],t[15],in[500010],lg2[1000010],pw2[23];
int L[300010],R[300010];
void add(int a,int b)
{
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dfs(int u,int fa)
{
	d[u]=d[fa]+1;
	p[++dfc]=u;
	in[u]=dfc;
	for(int i=h[u];~i;i=ne[i]){
		int j=e[i];
		if(j==fa)continue;
		dfs(j,u);
		p[++dfc]=u;
	}
}
int query(int l,int r)
{
	if(l>r)return 0;
	int k=lg2[r-l+1];
	int x=f[l][k],y=f[r-pw2[k]+1][k];
	if(d[x]<d[y])return x;
	return y;
}
int lca(int l,int r)
{
	l=in[l],r=in[r];
	if(l>r)swap(l,r);
	int lc=gt[l],rc=gt[r];
	if(lc==rc)return p[st[to[lc]][l-L[lc]][r-L[lc]]+L[lc]];
	int b=query(lc+1,rc-1);
	int a=p[st[to[lc]][l-L[lc]][R[lc]-L[lc]]+L[lc]];
	int c=p[st[to[rc]][0][r-L[rc]]+L[rc]];
	if(d[a]>d[b])a=b;if(d[a]>d[c])a=c;
	return a;
}
void init()
{
	int i,j,k;
	dfs(r,0);
	lg2[0]=-1;
	for(i=1;i<=dfc;++i)lg2[i]=lg2[i/2]+1;
	pw2[0]=1;
	for(i=1;i<=20;++i)pw2[i]=(pw2[i-1]<<1);
	int len=(lg2[n]+1)/4.0+1;
	int l=1,r;
	d[0]=0x3f3f3f3f;
	for(i=0;i<(1<<len);++i){
		for(j=0;j<len;++j)t[j]=((i>>j&1)<<1)-1;
		reverse(t,t+len);
		for(j=1;j<len;++j)t[j]+=t[j-1]; 
		for(j=0;j<len;++j){
			st[i][j][j]=j;
			for(k=j+1;k<len;++k){
				st[i][j][k]=st[i][j][k-1];
				if(t[st[i][j][k]]>t[k])st[i][j][k]=k;
			}
		}	
	}
	while(l<=dfc){	
		++num;
		r=min(l+len-1,dfc);
		L[num]=l,R[num]=r;
		for(i=l;i<=r;i++){
			gt[i]=num;
			if(d[f[num][0]]>d[p[i]])f[num][0]=p[i];
			if(i>l)to[num]=(to[num]<<1)|((d[p[i]]-d[p[i-1]]+1)>>1);
		}
		l=r+1;
	}
	for(j=1;j<=20;++j)
		for(i=1;i+pw2[j]-1<=num;++i){
			f[i][j]=f[i][j-1];
			if(d[f[i][j]]>d[f[i+pw2[j-1]][j-1]])
				f[i][j]=f[i+pw2[j-1]][j-1];
		}
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0); 
	int i,j,k;
	cin>>n>>q>>r;
	memset(h,-1,sizeof h);
	for(i=1;i<n;++i){
		int a,b,c;
		cin>>a>>b;
		add(a,b),add(b,a);
	}
	init();
	while(q--){
		int a,b;
		cin>>a>>b;
		cout<<lca(a,b)<<'\n';
	}
}

然后我后来把存图换成了 vector。。

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef unsigned long long ULL;
typedef long long LL;
typedef pair<int,int> PII;
int n,q,r;
vector<int> g[500010];
int d[500010],p[1000010],dfc,f[300010][23],to[300010],gt[1000010],num;
int st[2050][15][15],t[15],in[500010],lg2[1000010],pw2[23];
int L[300010],R[300010];
void dfs(int u,int fa)
{
	d[u]=d[fa]+1;
	p[++dfc]=u;
	in[u]=dfc;
	for(int j:g[u]){
		if(j==fa)continue;
		dfs(j,u);
		p[++dfc]=u;
	}
}
int query(int l,int r)
{
	if(l>r)return 0;
	int k=lg2[r-l+1];
	int x=f[l][k],y=f[r-pw2[k]+1][k];
	if(d[x]<d[y])return x;
	return y;
}
int lca(int l,int r)
{
	l=in[l],r=in[r];
	if(l>r)swap(l,r);
	int lc=gt[l],rc=gt[r];
	if(lc==rc)return p[st[to[lc]][l-L[lc]][r-L[lc]]+L[lc]];
	int b=query(lc+1,rc-1);
	int a=p[st[to[lc]][l-L[lc]][R[lc]-L[lc]]+L[lc]];
	int c=p[st[to[rc]][0][r-L[rc]]+L[rc]];
	if(d[a]>d[b])a=b;if(d[a]>d[c])a=c;
	return a;
}
void init()
{
	int i,j,k;
	dfs(r,0);
	lg2[0]=-1;
	for(i=1;i<=dfc;++i)lg2[i]=lg2[i/2]+1;
	pw2[0]=1;
	for(i=1;i<=20;++i)pw2[i]=(pw2[i-1]<<1);
	int len=(lg2[n]+1)/4.0+1;
	int l=1,r;
	d[0]=0x3f3f3f3f;
	for(i=0;i<(1<<len);++i){
		for(j=0;j<len;++j)t[j]=((i>>j&1)<<1)-1;
		reverse(t,t+len);
		for(j=1;j<len;++j)t[j]+=t[j-1]; 
		for(j=0;j<len;++j){
			st[i][j][j]=j;
			for(k=j+1;k<len;++k){
				st[i][j][k]=st[i][j][k-1];
				if(t[st[i][j][k]]>t[k])st[i][j][k]=k;
			}
		}	
	}
	while(l<=dfc){	
		++num;
		r=min(l+len-1,dfc);
		L[num]=l,R[num]=r;
		for(i=l;i<=r;i++){
			gt[i]=num;
			if(d[f[num][0]]>d[p[i]])f[num][0]=p[i];
			if(i>l)to[num]=(to[num]<<1)|((d[p[i]]-d[p[i-1]]+1)>>1);
		}
		l=r+1;
	}
	for(j=1;j<=20;++j)
		for(i=1;i+pw2[j]-1<=num;++i){
			f[i][j]=f[i][j-1];
			if(d[f[i][j]]>d[f[i+pw2[j-1]][j-1]])
				f[i][j]=f[i+pw2[j-1]][j-1];
		}
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0); 
	int i,j,k;
	cin>>n>>q>>r;
	for(i=1;i<n;++i){
		int a,b,c;
		cin>>a>>b;
		g[a].push_back(b),g[b].push_back(a);
	}
	init();
	while(q--){
		int a,b;
		cin>>a>>b;
		cout<<lca(a,b)<<'\n';
	}
}

神秘的挂成了90？？？？第9个点WA了