【模板】LCA

· · 个人记录

lca

倍增思想

code:

#include<bits/stdc++.h>
using namespace std;
#define Maxn 100005
int n,m,s,t;
int tot=1;
int hea[Maxn],ver[Maxn*2],nex[Maxn*2];
int d[Maxn],f[Maxn][20];
void add(int x,int y)
{
     ver[++tot]=y,nex[tot]=hea[x],hea[x]=tot;
     ver[++tot]=x,nex[tot]=hea[y],hea[y]=tot;
}
void bfs()
{
     queue<int> q;
     d[s]=1,q.push(s);
     while(!q.empty())
     {
         int cur=q.front();
         q.pop();
         for(int i=hea[cur];i;i=nex[i])
         {
             if(d[ver[i]]) continue;
             d[ver[i]]=d[cur]+1;
             f[ver[i]][0]=cur;
             for(int j=1;j<=t;j++)
                 f[ver[i]][j]=f[f[ver[i]][j-1]][j-1];
             q.push(ver[i]);
         }
     }
}
int lca(int x,int y)
{
     if(d[x]>d[y]) swap(x,y);
     for(int i=t;i>=0;i--)
         if(d[f[y][i]]>=d[x]) y=f[y][i];
     if(x==y) return x;
     for(int i=t;i>=0;i--)
         if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
     return f[x][0];
}
int main()
{
     //freopen("","r",stdin);
     //freopen("","w",stdout);
     scanf("%d%d%d",&n,&m,&s);
     t=(int)(log(n)/log(2))+1;
     for(int i=1;i<n;i++)
     {
         int u,v;
         scanf("%d%d",&u,&v);
         add(u,v);
     }
     bfs();
     for(int i=1;i<=m;i++)
     {
         int u,v;
         scanf("%d%d",&u,&v);
         printf("%d\n",lca(u,v));
     }
     //fclose(stdin);
     //fclose(stdout);
     return 0;
}

空间复杂度：O(n log n)

时间复杂度： 预处理 O(nlogn) 查询 O(logn)

重链剖分思想

code:

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define Maxn 500005
typedef long long ll;
inline int rd()
{
     int x=0;
     char ch,t=0;
     while(!isdigit(ch = getchar())) t|=ch=='-';
     while(isdigit(ch)) x=x*10+(ch^48),ch=getchar();
     return x=t?-x:x;
}
int n,m,s,tot;
int hea[Maxn],ver[Maxn*2],nex[Maxn*2];
int de[Maxn],si[Maxn],tp[Maxn],son[Maxn],Last[Maxn];
inline void add(int x,int y)
{
     ver[++tot]=y,nex[tot]=hea[x],hea[x]=tot;
}
void dfs1(int x,int fa)
{
     si[x]=1;
     for(int i=hea[x];i;i=nex[i])
     {
         if(ver[i]==fa) continue;
         de[ver[i]]=de[x]+1;
         dfs1(ver[i],x);
         Last[ver[i]]=x;
         si[x]+=si[ver[i]];
         if(si[ver[i]]>si[son[x]]) son[x]=ver[i];
     }
}
void dfs2(int x,int top)
{
     tp[x]=top;
     if(son[x]) dfs2(son[x],top);
     for(int i=hea[x];i;i=nex[i])
     {
         if(ver[i]==Last[x] || ver[i]==son[x]) continue;
         dfs2(ver[i],ver[i]);
     }
}
int Lca(int x,int y)
{
     while(tp[x]!=tp[y])
     {
         if(de[tp[x]]<de[tp[y]]) swap(x,y);
         x=Last[tp[x]];
     }
     if(de[x]>de[y]) swap(x,y);
     return x;
}
int main()
{
     //freopen("","r",stdin);
     //freopen("","w",stdout);
     n=rd(),m=rd(),s=rd();
     int u,v;
     for(int i=1;i<n;i++)
     {
         u=rd(),v=rd();
         add(u,v),add(v,u);
     }
     dfs1(s,0),dfs2(s,s);
     for(int i=1;i<=m;i++)
     {
         u=rd(),v=rd();
         printf("%d\n",Lca(u,v));
     }
     //fclose(stdin);
     //fclose(stdout);
     return 0;
}

空间复杂度：O(n)

时间复杂度： 预处理 O(n) 查询 O( < logn)