【朝夕的ACM筆記】目錄與索引

最近公共祖先-倍增算法

一、基本概念

最近公共祖先問題：對于給定的一顆有根樹，求其兩個節(jié)點(diǎn)的最近公共祖先。

祖先：節(jié)點(diǎn)本身、節(jié)點(diǎn)的父親、節(jié)點(diǎn)父親的父親……都是該節(jié)點(diǎn)的祖先。

公共祖先：兩個節(jié)點(diǎn)共同的祖先。

最近公共祖先(Lowest Common Ancestor)即LCA：距離根最遠(yuǎn)的公共祖先（也是深度最大的公共祖先）。

*LCA的重要性質(zhì)：

①若

是 的祖先，則 。

②若

不互為祖先，則 分別在 兩棵不同的子樹上。

③兩點(diǎn)的LCA必然在兩點(diǎn)間的最短路上，事實(shí)上兩點(diǎn)間的最短路就是從其中一點(diǎn)到LCA再到另一點(diǎn)。故

。

LCA的常見求法有：倍增算法、Tarjan算法、ST表算法、樹鏈剖分四種。

本篇介紹第一種：倍增算法。

二、算法思想

2.1 樸素算法

在講倍增算法前，我們先考慮一下暴力的樸素算法。

首先我們知道

。

所以我們可以先找到深度比較大的那個點(diǎn)，讓它先往上跳，直到兩點(diǎn)深度相同。

接著兩點(diǎn)一起往上跳，什么時候匯聚在一點(diǎn)，那點(diǎn)就是最近公共祖先。

但是樸素算法的時間復(fù)雜度是比較大的，最壞情況下相當(dāng)于

。即每次詢問都要遍歷整棵樹。

2.2 倍增算法

倍增算法是樸素算法的改進(jìn)算法。對于每個點(diǎn)，我們先求出它向上的第

個祖先。這樣再按照樸素算法向上跳時，跳躍的次數(shù)會減少很多。

需要注意的是，向上跳躍時，我們應(yīng)當(dāng)先考慮跳大的步子。

什么意思呢？

比如說我們要求一個節(jié)點(diǎn)向上的第13個祖先。

那我們應(yīng)該先跳8步，再跳4步，再跳1步。

對于預(yù)處理：

我們設(shè)

為點(diǎn) 的第 個祖先。

則顯然

。

接下來從根節(jié)點(diǎn)向下DFS，每跑到一個點(diǎn)，都可以求出這個點(diǎn)的前

個祖先。

倍增的轉(zhuǎn)移方程為

。

由于

有可能非整數(shù)，不好處理，所以可以統(tǒng)一求 。

對于求解LCA：

第一步先統(tǒng)一深度：

假設(shè)

，則 。

直接向下取整就好了，最多多跳一步。

然后一起向上跳，從大的步子開始，直到匯聚在同一點(diǎn)。

時間復(fù)雜度：

倍增算法預(yù)處理的時間復(fù)雜度是

，包含詢問內(nèi)的最差復(fù)雜度為 。

三、參考代碼

#include<bits/stdc++.h> #define ll long long using namespace std; vector<int>e[500005]; int dep[500005]; int fa[500005][25]; int lg[500005]; void dfs(int s,int fn)//s表示當(dāng)前點(diǎn)，fn是當(dāng)前點(diǎn)的父親節(jié)點(diǎn) {fa[s][0]=fn;//第一個祖先就是本身dep[s]=dep[fn]+1;//記錄點(diǎn)的深度for(int i=1;i<=lg[dep[s]]+1;i++)fa[s][i]=fa[fa[s][i-1]][i-1];//倍增轉(zhuǎn)移for(int i=0;i<e[s].size();i++)if(e[s][i]!=fn) dfs(e[s][i],s);//向下遍歷 } void pre(int n)//快速預(yù)處理log2 {lg[1]=0,lg[2]=1;for(int i=3;i<=n;i++) lg[i]=lg[i/2]+1; } int lca(int x,int y) {if(dep[x]<dep[y]) swap(x,y);//先保證x的深度大于等于ywhile(dep[x]>dep[y]) x=fa[x][lg[dep[x]-dep[y]]];//統(tǒng)一深度if(x==y) return x;//特判for(int i=lg[dep[x]];i>=0;i--)//從大步開始走if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];//一起往上跳return fa[x][0]; } int read()//快讀，增快讀入速度 {int re=0;char ch=getchar();while(ch<'0'||ch>'9')ch=getchar();while(ch>='0' && ch<='9'){re=re*10+ch-'0';ch=getchar();}return re; } int main() {int n,m,s;//樹的點(diǎn)數(shù)、詢問次數(shù)、根節(jié)點(diǎn)n=read();m=read();s=read();for(int i=1;i<=n-1;i++){int x,y;x=read(),y=read();e[x].push_back(y);e[y].push_back(x);//樹是無向圖}pre(n);//預(yù)處理log2dfs(s,0);//dfs預(yù)處理fa數(shù)組for(int i=1;i<=m;i++){int a,b;a=read(),b=read();printf("%dn",lca(a,b));}return 0; }

總結(jié)

以上是生活随笔為你收集整理的tarjan算法_【朝夕的ACM笔记】树上问题-最近公共祖先-倍增算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。