真 · 玄学事件
查看原帖
真 · 玄学事件
1161106
yanzhouxuzihao楼主2024/8/8 22:29

求助!在代码调试时的输出忘关了,样例是对的,但把调试的输出注释了之后,答案输出变了

#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)
   	{
//			cout<<e[i].v;
   		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;
}

2024/8/8 22:29
加载中...