交洛谷板子题目的时候是错了五个点,开了 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;
}