萌新求助倍增$LCA$
查看原帖
萌新求助倍增$LCA$
294736
bovine__kebi楼主2020/5/17 11:08

RT,禁止无意义回复

#pragma GCC optimize("Ofast","-funroll-loops","-fdelete-null-pointer-checks")
#pragma GCC target("ssse3","sse3","sse2","sse","avx2","avx")
#include<bits/stdc++.h>
using namespace std;
const int maxn=500005;
int depth[maxn];
int fa[maxn][25],head[maxn];
double log2n;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21], *p1 = buf, *p2 = buf;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
	return x*f;
}
inline void print(int x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) print(x/10);
    putchar(x%10+'0');
}
struct node
{
	int next,to;
}edge[maxn<<1];
int cnt=0;
void add_edge(int u,int v)
{
	edge[++cnt].to=v;
	edge[cnt].next=head[u];
	head[u]=cnt;
}
inline void getdepth(int now,int father)
{
	depth[now]=depth[father]+1;
	fa[now][0]=father;
	for(int i=1;(1<<i)<=depth[now];i++) fa[now][i]=fa[fa[now][i-1]][i-1];
	for(int i=head[now];i;i=edge[i].next)
	{
		if(edge[i].to==father)continue;
		getdepth(edge[i].to,now); 
	} 
}
inline int LCA(int u,int v)
{
	int deepv=depth[v],deepu=depth[u];
	if(depth[v]!=depth[u])
	{
		if(depth[v]>depth[u]){
			swap(u,v);
			swap(deepv,deepu);
		}
		int d=deepu-deepv;
		for(int i=0;i<=log2n;i++)
			if((1<<i)&d)u=fa[u][i];
	}
	for(int i=log2n;i>=0;i--)
	{
		if(depth[fa[u][i]]<=0)continue;
		if(fa[u][i]==fa[v][i])continue;
		else u=fa[u][i],v=fa[v][i];
	}
	return fa[u][0];
}
int main()
{
	int n,m,hd;
	n=read();m=read();hd=read(); 
	for(int i=1;i<=n;i++)
	{
		int u,v;u=read();v=read();
		add_edge(u,v);add_edge(v,u); 
	}
	getdepth(hd,0);
	log2n=log2(n)/log2(2)+0.5;
	for(int i=1;i<=m;i++)
	{
		int u,v;u=read();v=read();
		print(LCA(u,v));putchar('\n');
	}
}

好像问题是跳不出循环/fad

2020/5/17 11:08
加载中...