# LCA:倍加与tarjan

www.MyException.Cn  网友分享于：2013-10-08  浏览：0次
LCA:倍增与tarjan

f[i][j]=f[f[i][j-1]][j-1]

---------------------------------------------------------分割线-----------------------------------------------------

```#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#define N 500005
using namespace std;
struct Edge{
int from,to,next;
}edge[N*2];
{
char ch=getchar();int num=0;
if(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9')
{num=num*10+ch-'0';
ch=getchar();}
return num;
}
int anum=1;
{edge[anum].to=y;
void dfs(int u)
{
{
int ne=edge[i].to;
if(d[ne]==0)
{d[ne]=d[u]+1;
f[ne][0]=u;
dfs(ne);}
}
}
void init()
{
for(int i=1;i<=19;i++)
{
for(int j=1;j<=n;j++)
{f[j][i]=f[f[j][i-1]][i-1];}
}
}
int lca(int a,int b)
{
if(d[a]<d[b]) swap(a,b);
for(int i=19;i>=0;i--)
{if(d[f[a][i]]>=d[b])
a=f[a][i];}
if(a==b) return a;
for(int i=19;i>=0;i--)
if(f[a][i]!=f[b][i])
a=f[a][i],b=f[b][i];
return f[a][0];
}
int main()
{
for(int i=1;i<n;i++)
{int x,y;
d[s]=1;
dfs(s);init();
for(int i=1;i<=m;i++)
{int a,b;
printf("%d\n",lca(a,b));}
return 0;
}```

`-----------------------------------------------------------------分割线-------------------------------------------------------------------------------`

```#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#define N 500005
#define M 1000001
using namespace std;
int n,m,s,cnt1,cnt2;
bool used[N];
struct edge{
int v,num,next;
}e1[M],e2[M];
}v1[N],v2[N];
void before()
{
memset(v1,-1,sizeof(v1));
memset(v2,-1,sizeof(v2));
memset(used,false,sizeof(used));
}
int find(int x)
{
}
void together(int x,int y)
{
int f1=find(x);
int f2=find(y);
if(f1!=f2)
}
{
e1[cnt1].v=y;
}
{
e2[cnt2].v=y;
e2[cnt2].num=z;
}
void tarjan(int u)
{
used[u]=true;
{
int v=e1[i].v;
if(used[v]) continue;
tarjan(v);
together(u,v);
}
int sum;
{
int v=e2[i].v;
sum=e2[i].num;
if(used[v])
ans[sum]=find(v);
}
}
int main()
{
int u,v;
scanf("%d%d%d",&n,&m,&s);
before();
int nn=n;
nn--;
while(nn--)
{
scanf("%d%d",&u,&v);
}
for(int i=1;i<=m;i++)
{
scanf("%d%d",&u,&v);