今天是2017/7/10,DCDCBigBig的第二十三篇博文
树上倍增（LCA）
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
struct edge{
int v,next;
}a[
100001];
int n,q,u,v,rt,tot=
0,head[
100001],fa[
100001][
31],dep[
100001];
bool vis[
100001];
void add(
int u,
int v){
a[++tot].v=v;
a[tot].next=head[u];
head[u]=tot;
}
void cal_dep(
int u){
vis[u]=
true;
for(
int tmp=head[u];tmp!=-
1;tmp=a[tmp].next){
int v=a[tmp].v;
if(!vis[v]){
dep[v]=dep[u]+
1;
cal_dep(v);
}
}
}
void cal(){
for(
int j=
1;j<=
30;j++){
for(
int i=
1;i<=n;i++){
fa[i][j]=fa[fa[i][j-
1]][j-
1];
}
}
}
int lca(
int x,
int y){
if(dep[x]<dep[y]){
swap(x,y);
}
int s=dep[x]-dep[y];
for(
int i=
0;i<
30;i++){
if((
1<<i)&s)x=fa[x][i];
}
if(x==y)
return x;
for(
int i=
29;i>=
0;i--){
if(fa[x][i]!=fa[y][i]){
x=fa[x][i];
y=fa[y][i];
}
}
return fa[x][
0];
}
int main(){
memset(head,-
1,
sizeof(head));
memset(fa,
0,
sizeof(fa));
memset(dep,
0,
sizeof(dep));
memset(vis,
0,
sizeof(vis));
scanf(
"%d%d",&n,&q);
for(
int i=
1;i<n;i++){
scanf(
"%d%d",&u,&v);
add(u,v);
fa[v][
0]=u;
}
dep[
1]=
1;
cal_dep(
1);
cal();
for(
int i=
1;i<=q;i++){
scanf(
"%d%d",&u,&v);
printf(
"%d\n",lca(u,v));
}
return 0;
}
笑
