dfs2死循环了
#include<bits/stdc++.h>
using namespace std;
const int N = 200000+10;
vector<int> G[N] ;
int dep[N],fa[N],hson[N],sz[N],top[N],dfn[N];
void dfs1(int u,int p){//u当前访问到的,p父节点。
fa[u] = p;
sz[u] = 1;
dep[u] = dep[p]+1;
int maxh = 0;
for(int i = 0;i < G[u].size();i++){
int v = G[u][i];
if(v == p)continue;
dfs1(v,u);
sz[u]+=sz[v];
if(maxh < sz[v]){
hson[u] = v;
maxh = sz[v];
}
}
if(sz[u] == 1)hson[u] == -1;
}
int cnt;//记录是第几次访问
void dfs2(int u,int p){
//先遍历重儿子
cnt++;
dfn[u] = cnt;
if(hson[u] == -1)return;
top[hson[u]] = top[u];
dfs2(hson[u],u);
for(int i = 0;i < G[u].size();i++){
int v = G[u][i];
if(v == p || hson[u] == v)continue;
top[v] = v;
dfs2(v,u);
}
}
int lca(int u,int v){
if(top[u] == top[v])return dep[u]<dep[v] ? u : v;//那个深度小就取哪个。
if(dep[top[u]]<dep[top[v]]) return lca(u,fa[top[v]]);
else return lca(fa[top[u]],v);
//因为他是要跳到top的父亲上所以要比较两个top的深度;
}
int main(){
int n;
cin>>n;
for(int i = 1;i <= n-1;i++){
int u,v;
cin>>u>>v;
G[u].push_back(v);
G[v].push_back(u);
}
dfs1(1,1);
dfs2(1,1);
int q;
cin>>q;
while(q--){
int u,v;
cin>>u>>v;
cout<<lca(u,v)<<endl;
}
return 0;
}