请问我这份LCA哪里有错啊
  • 板块学术版
  • 楼主wweiyi
  • 当前回复4
  • 已保存回复4
  • 发布时间2021/11/11 19:21
  • 上次更新2023/11/4 00:52:29
查看原帖
请问我这份LCA哪里有错啊
136889
wweiyi楼主2021/11/11 19:21

交洛谷板子题目的时候是错了五个点,开了 long long

但是这个板子作为板子套进其他题里面基本全都是对的

所以这个板子有什么问题吗

求神犇帮忙看看

谢谢!

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
#define int long long
using namespace std;
const int maxn=500005;
int n,m,s;
struct edge{
	int e,next;
}ed[maxn<<1];
int en,first[maxn];
void add_edge(int s,int e)
{
	en++;
	ed[en].next=first[s];
	first[s]=en;
	ed[en].e=e;
}

int fa[maxn][25];
int dep[maxn];
void dfs1(int x)
{
	for(int i=1;(1<<i)<=dep[x];i++)
	fa[x][i]=fa[fa[x][i-1]][i-1];
	for(int i=first[x];i;i=ed[i].next)
	{
		int e=ed[i].e;
		if(e==fa[x][0]) continue;
		fa[e][0]=x;
		dep[e]=dep[x]+1;
		dfs1(e);
	}
}
int get_lca(int x,int y)
{
	if(x==y) return x;
	if(dep[x]<dep[y]) swap(x,y);
	int t=log(dep[x]-dep[y])/log(2);
	for(int i=t;i>=0;i--)
	{
		if(dep[fa[x][i]]>=dep[y])
		x=fa[x][i];
		if(x==y)
		return x;
	}
	t=log(dep[x])/log(2);
	for(int i=t;i>=0;i--)
	{
		if(fa[x][i]!=fa[y][i])
		x=fa[x][i],y=fa[y][i];
	}
	return fa[x][0];
}
signed main()
{
	cin>>n>>m>>s;
	for(int i=1;i<=n-1;i++)
	{
		int x,y;
		cin>>x>>y;
		add_edge(x,y);
		add_edge(y,x);
	}
	dfs1(s);
	fa[s][0]=0;
	while(m--)
	{
		int a,b;
		cin>>a>>b;
		cout<<get_lca(a,b)<<'\n';
	}
	return 0;
}
2021/11/11 19:21
加载中...