求助!在代码调试时的输出忘关了,样例是对的,但把调试的输出注释了之后,答案输出变了
#include<bits/stdc++.h>
using namespace std;
struct Edge{
int u,v,w,next;
}e[610001];
int n,m,num,u,v,w,xu,s;
int head[310000],fa[310000],big_son[310000];
int son_num[310000],deep[310000],dfn[310000],rnk[310000],top[310000];
bool bz[310000];
int dfs1(int a,int dep)
{
deep[a]=dep;
bool flag=1;
int maxn=0,temp,num;
for(int i=head[a];i!=0;i=e[i].next)
{
if(bz[e[i].v]==0)
{
bz[e[i].v]=1;
fa[e[i].v]=a;
flag=0;
num=dfs1(e[i].v,dep+1);
son_num[a]+=num;
if(num>maxn)
{
maxn=num;
temp=e[i].v;
}
}
}
big_son[a]=temp;
if(flag) return 1;
return son_num[a]+1;
}
void dfs2(int a,int dep)
{
xu++;
dfn[a]=xu;
rnk[dfn[a]]=a;
deep[a]=dep;
if(big_son[a]!=0)
{
bz[big_son[a]]=1;
top[big_son[a]]=top[a];
dfs2(big_son[a],dep+1);
}
for(int i=head[a];i!=0;i=e[i].next)
{
if(bz[e[i].v]==0)
{
bz[e[i].v]=1;
top[e[i].v]=e[i].v;
dfs2(e[i].v,dep+1);
}
}
return ;
}
void add(int u,int v,int w)
{
e[++num].next=head[u];
e[num].u=u;
e[num].v=v;
e[num].w=w;
head[u]=num;
}
int lca(int x,int y)
{
while(top[x]!=top[y])
{
if (deep[top[x]]>deep[top[y]])
x=fa[top[x]];
else
y=fa[top[y]];
}
if(deep[x]<deep[y])
return x;
else
return y;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m>>s;
for(int i=1;i<n;i++)
{
cin>>u>>v;
add(u,v,1);
add(v,u,1);
}
bz[s]=1;
dfs1(s,0);
memset(bz,0,sizeof(bz));
bz[s]=1;
top[s]=s;
fa[s]=s;
dfs2(s,0);
for(int i=1;i<=m;i++)
{
int x,y;
cin>>x>>y;
cout<<lca(x,y)<<"\n";
}
return 0;
}