蒟蒻树剖全RE求助!
查看原帖
蒟蒻树剖全RE求助!
67912
白厶冯弓吿氵楼主2020/7/29 17:00

本地AC提交RE?奇奇怪怪。

各位大佬请帮忙看看?谢谢

#include<bits/stdc++.h>
using namespace std;
int n,m,r,p,cnt,cur,dep[1000005],siz[1000005],fa[1000005],hson[1000005],top[1000005];
vector<int> e[1000005]; 
int dfs1(int u,int f)
{
	dep[u]=dep[f]+1;
	siz[u]=1;
	fa[u]=f;
	for(int i=e[u].size()-1;i>=0;i--) 
	{
		int v=e[u][i];
		if(v==f) continue;
		dfs1(v,u);
		siz[u]+=siz[v];
		if(siz[hson[u]]<siz[v]) hson[u]=v; 
	}
}
void dfs2(int u,int f)
{
	top[u]=f;
	if(siz[u]==1) return ;
	dfs2(hson[u],f);
	for(int i=e[u].size()-1;i>=0;i--)
	{
		int v=e[u][i];
		if(v==hson[u] || v==fa[u]) continue;
		dfs2(v,v);
	}
}
int LCA(int x,int y)
{
//	cout<<x<<" "<<y<<" "<<a[x].top<<" "<<a[y].top<<endl; 
	if(top[x]!=top[y])
	{
		if(dep[top[x]]>dep[top[y]]) return LCA(fa[top[x]],y);
		else return LCA(x,fa[top[y]]);
	}
	else
	{
		if(dep[x]>dep[y]) return y;
		else return x;
	}
}
int main()
{
	scanf("%d%d%d",&n,&m,&r); 
	for(int i=1;i<n;i++)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		e[u].push_back(v);
		e[v].push_back(u);
	}
	dfs1(r,0); 
	dfs2(r,r);
	while(m--)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		printf("%d\n",LCA(x,y));
	}
	return 0;
} 
2020/7/29 17:00
加载中...