题解 P3379 【【模板】最近公共祖先（LCA）】

· · 题解

刚学了st写法，写一篇题解练练手

首先，我们按照dfs的过程得到一个欧拉序（访问到一个数就加到序列末尾 （包括回溯） ）

结合图理解一下欧拉序

然后我们观察上图，感性理解一下就能发现lca是fir[x],fir[y]中dep最小的（fir为第一次出现的位置）

所以我们就得到了一个rmq问题：

在fir[x]~fir[y]中，dep最小的是哪个

显然，我们可以用st表维护，然后查询就可以做到O(1)了

感性理解，你一个数，最多在被访问到时tim++，回溯时，父亲tim++，所以st表开两倍

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+25;
int n,m,s,st[N*2][20],dfn[N],fir[N],tim,dep[N],fa[N];
struct edge
{
    int next,to;
}p[2*N];
int head[N],num;
void ad(int x,int y)
{
    p[++num]=edge{head[x],y};
    head[x]=num;
}
void dfs(int u)
{
    dfn[++tim]=u; //欧拉序中第i个数是啥 
    if(!fir[u]) fir[u]=tim; //u在欧拉序中第一次出现的位置 
    st[tim][0]=u; //st表 
    for(int i=head[u];i;i=p[i].next)
    {
        int v=p[i].to;
        if(v==fa[u]) continue;
        fa[v]=u;
        dep[v]=dep[u]+1;
        dfs(v);
        dfn[++tim]=u;
        st[tim][0]=u;
    }
}
int lca(int x,int y)
{
    int l=fir[x],r=fir[y];
    if(r<l) swap(l,r);
    int lg=(log2(r-l+1));
//  printf("@%d %d %d\n",l,r,lg);
//  printf("@%d %d %d %d %d\n",l,r,lg,r-l+1,log2(r-l+1));
    return dep[st[l][lg]]>dep[st[r-(1<<lg)+1][lg]]?st[r-(1<<lg)+1][lg]:st[l][lg];
}
int main() 
{
    cin>>n>>m>>s;
    for(int i=1;i<n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        ad(x,y);
        ad(y,x);
    }
    dfs(s);
//  for(int i=1;i<=tim;i++) st[i][0]=dfn[i];
//  for(int i=1;i<=n;i++) printf("#%d %d %d\n",i,dfn[i],fir[i]);
    for(int j=1;j<=20;j++)
        for(int i=1;i+(1<<j)-1<=tim;i++)
            if(dep[st[i][j-1]]>dep[st[i+(1<<(j-1))][j-1]]) st[i][j]=st[i+(1<<(j-1))][j-1];
            else st[i][j]=st[i][j-1];
//  for(int i=1;i<=n;i++) for(int j=0;j<=2;j++) printf("%d %d %d\n",i,j,st[i][j]);
    while(m--)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        printf("%d\n",lca(x,y));
    }
    return 0;
}