暴力.用fa是否被标记判断节点是否被遍历过，预处理出现问题.

#include<bits/stdc++.h>
using namespace std;
#define xx 500010
int n,m,s,fa[xx],dp[xx];
bool vis[xx];
vector<int>g[xx];
void dfs(int x,int f,int d){
	fa[x]=f;dp[x]=d;vis[x]=1;
	for(int i=0;i<g[x].size();i++)if(!fa[g[x][i]])dfs(g[x][i],x,d+1);
	return;
}
int solve(int x,int y){
	int c=abs(dp[x]-dp[y]);
	if(dp[x]<dp[y])while(c--)y=fa[y];
	if(dp[y]<dp[x])while(c--)x=fa[x];
	while(x!=y)x=fa[x],y=fa[y];
	return x;
}
int main(){
	cin>>n>>m>>s;
	for(int i=1;i<n;i++){
		int u,v;cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs(s,0,1);
	while(m--){
		int x,y;cin>>x>>y;
		cout<<solve(x,y)<<'\n';
	}
//	for(int i=1;i<=n;i++)cout<<dp[i]<<' ';
	return 0;
}

将

	for(int i=0;i<g[x].size();i++)if(!fa[g[x][i]])dfs(g[x][i],x,d+1);

改为

	for(int i=0;i<g[x].size();i++)if(!vis[g[x][i]])dfs(g[x][i],x,d+1);

就预处理正确了

求大佬解释,蒟蒻CPU烧了（