简介

最近公共祖先 \(lca(a,b)\) 指的是a到根的路径和b到n的路径的深度最大的公共点.

定理. 以 \(r\) 为根的树上的路径 \((a,b) = (r,a) + (r,b) - 2 * (r,fa(lca))\). (树上差分)

求法

tarjan

离线算法, 总时间 \(O(n+q)\). (q表示询问次数)

//利用前向星存储询问struct te{int t,pr,lca;}edge[1000050],qedge[1000050];int head[500050],pe=1,qhead[500050],pq=1;void adde(int f,int t){    edge[++pe].t=t;    edge[pe].pr=head[f];    head[f]=pe; }void addq(int f,int t){    qedge[++pq].t=t;    qedge[pq].pr=qhead[f];    qhead[f]=pq;}//并查集int fa[500050];int find(int p){return p==fa[p]?p:fa[p]=find(fa[p]);}void merge(int l,int r){fa[r]=l;}//merge r to l//tarjanint vi[500050];void tar(int p){    vi[p]=1;    for(int i=head[p];i;i=edge[i].pr){        if(vi[edge[i].t])continue;        tar(edge[i].t);        merge(p,edge[i].t);    }    for(int i=qhead[p];i;i=qedge[i].pr)        if(vi[qedge[i].t])            qedge[i].lca=qedge[i^1].lca=find(qedge[i].t);}

倍增

\(O(n\log n)\)预处理, \(O(\log n)\) 查询, \(O(n\log n)\)空间. 由于利用结合律, 可以维护一些链上信息. 可以动态维护.

int fa[nsz][20],dep[nsz]{-1};//动态维护void addfa(int p,int f){    dep[p]=dep[f]+1;    fa[p][0]=f;    rep(i,1,18)fa[p][i]=fa[fa[p][i-1]][i-1];}//静态void init(){    dfs(1,0); //get fa[i][0]    rep(i,1,18)rep(j,1,n)fa[j][i]=fa[fa[j][i-1]][i-1];}int lca(int a,int b){    if(dep[a]
    
     =dep[b])a=fa[a][i];    if(a==b)return a;    repdo(i,18,0)if(fa[a][i]!=fa[b][i])a=fa[a][i],b=fa[b][i];    return fa[a][0];}
    

欧拉序+rmq

\(O(n\log n)\)预处理, \(O(1)\) 查询, \(O(n\log n)\)空间.

int l2n[nsz*3+50];int eul[nsz*3],cnt=0,vis[nsz],d[nsz];int stt[nsz*3][21];void dfs(int u,int fa){    eul[++cnt]=u;    if(vis[u]==0)vis[u]=cnt,d[u]=d[fa]+1;    for(int i=hd[u],v=edge[i].t;i;i=edge[i].pr,v=edge[i].t){        if(v==fa)continue;        dfs(v,u);        eul[++cnt]=u;    }}int dmin(int a,int b){return d[a]<=d[b]?a:b;}void rmq(){    rep(i,1,cnt)stt[i][0]=eul[i];    rep(j,1,l2n[pe]){        rep(i,1,pe+1-(1<
    
     y)swap(x,y);    return stqu(x,y);}
    

树链剖分

\(O(n)\)预处理, \(O(\log n)\) 查询, \(O(n)\)空间. 由于利用结合律, 可以维护一些链上信息.

int dep[nsz],sz[nsz],son[nsz],fa[nsz],top[nsz];void dfs1(int p,int f){    sz[p]=1,dep[p]=dep[f]+1,fa[p]=f;    for(int i=hd[p],v=edge[i].t;i;i=edge[i].pr,v=edge[i].t){        if(v==f)continue;        dfs1(v,p);        sz[p]+=sz[v];        if(son[p]==0||sz[son[p]]
    
     =dep[top[y]])x=fa[top[x]];        else y=fa[top[y]];    }    return dep[x]