最近公共祖先(LCA-tarjan/RMQ/倍增)

在一棵沒有環(huán)的樹上晰甚，每個(gè)節(jié)點(diǎn)肯定有其父親節(jié)點(diǎn)和祖先節(jié)點(diǎn)蓖捶，而最近公共祖先俊鱼，就是兩個(gè)節(jié)點(diǎn)在這棵樹上深度最大的公共的祖先節(jié) 換句話說并闲，就是兩個(gè)點(diǎn)在這棵樹上距離最近的公共祖先節(jié)點(diǎn)帝火。
有人可能會(huì)問：那他本身或者其父親節(jié)點(diǎn)是否可以作為祖先節(jié)點(diǎn)呢蠢壹？答案是肯定的图贸，很簡單疏日，按照人的親戚觀念來說，你的父親也是你的祖先神凑，而LCA還可以將自己視為祖先節(jié)點(diǎn)鹃唯。
求LCA算法常用的三種tarjan/倍增/ST

tarjan求LCA原理：

聲明下面內(nèi)容參考：大佬傳送門https://www.cnblogs.com/JVxie/p/4854719.html
　舉個(gè)例子吧竟终，如下圖所示４和５的最近公共祖先是２，５和３的最近公共祖先是１洛巢，２和１的最近公共祖先是１〉芡恚　

這就是最近公共祖先的基本概念了，那么我們該如何去求這個(gè)最近公共祖先呢瑟押？

什么是Tarjan(離線)算法呢多望？顧名思義便斥，就是在一次遍歷中把所有詢問一次性解決枢纠，所以其時(shí)間復(fù)雜度是O(n+q)。

Tarjan算法的優(yōu)點(diǎn)在于相對穩(wěn)定木西，時(shí)間復(fù)雜度也比較居中八千，也很容易理解恋捆。

下面詳細(xì)介紹一下Tarjan算法的基本思路：

1. 任選一個(gè)點(diǎn)為根節(jié)點(diǎn)，從根節(jié)點(diǎn)開始昭卓。

2.遍歷該點(diǎn)u所有子節(jié)點(diǎn)v能颁，并標(biāo)記這些子節(jié)點(diǎn)v已被訪問過伙菊。

3.若是v還有子節(jié)點(diǎn)占业，返回2，否則下一步念恍。

4.合并v到u上。

5.尋找與當(dāng)前點(diǎn)u有詢問關(guān)系的點(diǎn)v疗疟。

6.若是v已經(jīng)被訪問過了，則可以確認(rèn)u和v的最近公共祖先為v被合
并到的父親節(jié)點(diǎn)a店诗。

遍歷的話需要用到dfs來遍歷(我相信來看的人都懂吧...)庞瘸，至于合并擦囊，最優(yōu)化的方式就是利用并查集來合并兩個(gè)節(jié)點(diǎn)。

void dfs(int u)
{
    vis[u]=1;
    for(int i=0;i<ve[u].size();i++)//遍歷子節(jié)點(diǎn)
    {
        int v=ve[u][i];
        dfs(ve[u][i]);//還有子節(jié)點(diǎn)
        ouin(u,ve[u][i]);//合并父子節(jié)點(diǎn)
    }
    for(int j=0;j<pp[u].size();j++)//尋找當(dāng)前點(diǎn)u有詢問關(guān)系的點(diǎn)
    {
        int w=pp[u][j];
        if(vis[w]==1)//如果點(diǎn)已經(jīng)被訪問泌类，就確認(rèn)父節(jié)點(diǎn)是誰
        {
            ans=find(w);
        }
    }
}

建議拿著紙和筆跟著我的描述一起模擬Ｈ姓ァ枢希！

假設(shè)我們有一組數(shù)據(jù) 9個(gè)節(jié)點(diǎn) 8條邊聯(lián)通情況如下：

1--2苞轿，1--3搬卒，2--4契邀，2--5坯门，3--6欠橘，5--7现恼，5--8痹升，7--9 即下圖所示的樹

設(shè)我們要查找最近公共祖先的點(diǎn)為9--8，4--6艺配，7--5转唉，5--3；

設(shè)f[]數(shù)組為并查集的父親節(jié)點(diǎn)數(shù)組乔夯，初始化f[i]=i末荐，vis[]數(shù)組為是否訪問過的數(shù)組眶熬，初始為0;

下面開始模擬過程：

取1為根節(jié)點(diǎn)娜氏，往下搜索發(fā)現(xiàn)有兩個(gè)兒子2和3；

先搜2茂腥，發(fā)現(xiàn)2有兩個(gè)兒子4和5，先搜索4帕胆，發(fā)現(xiàn)4沒有子節(jié)點(diǎn)，則尋找與其有關(guān)系的點(diǎn)驯用；

發(fā)現(xiàn)6與4有關(guān)系记餐，但是vis[6]=0片酝，即6還沒被搜過雕沿，所以不操作审轮；

發(fā)現(xiàn)沒有和4有詢問關(guān)系的點(diǎn)了疾渣，返回此前一次搜索稳衬，更新vis[4]=1；

表示4已經(jīng)被搜完街夭，更新f[4]=2板丽，繼續(xù)搜5猖辫，發(fā)現(xiàn)5有兩個(gè)兒子7和8;

先搜7，發(fā)現(xiàn)7有一個(gè)子節(jié)點(diǎn)9辛萍，搜索9贩毕，發(fā)現(xiàn)沒有子節(jié)點(diǎn)辉阶，尋找與其>有關(guān)系的點(diǎn)睛藻；

發(fā)現(xiàn)8和9有關(guān)系，但是vis[8]=0,即8沒被搜到過，所以不操作包券；

發(fā)現(xiàn)沒有和9有詢問關(guān)系的點(diǎn)了溅固，返回此前一次搜索询吴，更新vis[9]=1猛计；

表示9已經(jīng)被搜完，更新f[9]=7藕赞，發(fā)現(xiàn)7沒有沒被搜過的子節(jié)點(diǎn)了斧蜕，尋找>與其有關(guān)系的點(diǎn)；

發(fā)現(xiàn)5和7有關(guān)系风钻，但是vis[5]=0，所以不操作布朦；

發(fā)現(xiàn)沒有和7有關(guān)系的點(diǎn)了是趴，返回此前一次搜索，更新vis[7]=1肛搬；

表示7已經(jīng)被搜完毕贼，更新f[7]=5温赔，繼續(xù)搜8，發(fā)現(xiàn)8沒有子節(jié)點(diǎn)鬼癣，則尋找與其有關(guān)系的點(diǎn)陶贼；

發(fā)現(xiàn)9與8有關(guān)系，此時(shí)vis[9]=1待秃，則他們的最近公共祖先為>find(9)=5骇窍；

(find(9)的順序?yàn)閒[9]=7-->f[7]=5-->f[5]=5 return 5;)

發(fā)現(xiàn)沒有與8有關(guān)系的點(diǎn)了，返回此前一次搜索腹纳，更新vis[8]=1淹辞；

表示8已經(jīng)被搜完央星，更新f[8]=5颓遏，發(fā)現(xiàn)5沒有沒搜過的子節(jié)點(diǎn)了，尋找與其有關(guān)系的點(diǎn)贝咙；

發(fā)現(xiàn)7和5有關(guān)系，此時(shí)vis[7]=1，所以他們的最近公共祖先為find(7)=5蠢护；

(find(7)的順序?yàn)閒[7]=5-->f[5]=5 return 5;)

又發(fā)現(xiàn)5和3有關(guān)系懈凹，但是vis[3]=0威沫，所以不操作颈墅，此時(shí)5的子節(jié)點(diǎn)全
部搜完了；

返回此前一次搜索腿箩，更新vis[5]=1滑潘，表示5已經(jīng)被搜完粹舵，更新f[5]=2堰塌；

發(fā)現(xiàn)2沒有未被搜完的子節(jié)點(diǎn)邀桑，尋找與其有關(guān)系的點(diǎn)照弥；

又發(fā)現(xiàn)沒有和2有關(guān)系的點(diǎn)机打，則此前一次搜索，更新vis[2]=1；

表示2已經(jīng)被搜完氮昧，更新f[2]=1专筷，繼續(xù)搜3责嚷，發(fā)現(xiàn)3有一個(gè)子節(jié)點(diǎn)6炮叶；

搜索6，發(fā)現(xiàn)6沒有子節(jié)點(diǎn)陡蝇，則尋找與6有關(guān)系的點(diǎn)鲁纠，發(fā)現(xiàn)4和6有關(guān)系；

此時(shí)vis[4]=1，所以它們的最近公共祖先為find(4)=1;

(find(4)的順序?yàn)閒[4]=2-->f[2]=2-->f[1]=1 return 1;)

發(fā)現(xiàn)沒有與6有關(guān)系的點(diǎn)了，返回此前一次搜索，更新vis[6]=1，表示6已>經(jīng)被搜完了葬项；

更新f[6]=3落包，發(fā)現(xiàn)3沒有沒被搜過的子節(jié)點(diǎn)了盅称，則尋找與3有關(guān)系的點(diǎn)掖蛤；

發(fā)現(xiàn)5和3有關(guān)系撮弧，此時(shí)vis[5]=1，則它們的最近公共祖先為>find(5)=1；

(find(5)的順序?yàn)閒[5]=2-->f[2]=1-->f[1]=1 return 1;)

發(fā)現(xiàn)沒有和3有關(guān)系的點(diǎn)了席吴，返回此前一次搜索，更新vis[3]=1；

更新f[3]=1昧绣，發(fā)現(xiàn)1沒有被搜過的子節(jié)點(diǎn)也沒有有關(guān)系的點(diǎn)发绢，此時(shí)可以退出整個(gè)dfs了。

經(jīng)過這次dfs我們得出了所有的答案垄琐，有沒有覺得很神奇呢边酒？是否對Tarjan算法有更深層次的理解了呢？

#include<iostream>
#include<cstdio>
#include<string.h>
#include<vector>
#define MAN 10005
using namespace std;
vector<int> ve[MAN];
vector<int> pp[MAN];
int fa[MAN],vis[MAN];
int ans,n;
int find(int x)
{
    if(x==fa[x])
    {
        return x;
    }
    else
    {
        return find(fa[x]);
    }
}
void ouin(int x,int y)
{
    x=find(x);
    y=find(y);
    if(x!=y)
    {
        fa[y]=x;
    }
}
void init( )
{
    for(int i=0;i<=n;i++)
    {
        fa[i]=i;
        ve[i].clear();
        pp[i].clear();
        vis[i]=0;
    }
}
void dfs(int u)
{
    vis[u]=1;
    for(int i=0;i<ve[u].size();i++)
    {
        int v=ve[u][i];
        dfs(ve[u][i]);
        ouin(u,ve[u][i]);
    }
    for(int j=0;j<pp[u].size();j++)
    {
        int w=pp[u][j];
        if(vis[w]==1)
        {
            //cout<<w<<endl;
            ans=find(w);
        }
    }
}
int main( )
{
    int t,x,y,a,b;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        init( );
        for(int i=1;i<=n-1;i++)
        {
            scanf("%d%d",&x,&y);
            ve[x].push_back(y);
            vis[y]=1;
        }
        scanf("%d%d",&a,&b);
        pp[a].push_back(b);
        pp[b].push_back(a);
        for(int i=1;i<=n;i++)
        {
            if(vis[i]==0)
            {
                memset(vis,0,sizeof(vis));
                dfs(i);
                break;
            }
        }
        // for(int i=1;i<=n;i++)
        // {
        //  cout<<fa[i]<<" ";
        // }
        cout<<endl;
        printf("%d\n",ans);
    }
    return 0;
}

RMQ與LCA

參考大佬傳送門https://www.cnblogs.com/scau20110726/archive/2013/05/26/3100812.html
首先闡述一下RMQ怎么能和LCA扯上關(guān)系呢狸窘？現(xiàn)在思考一下墩朦，最近公共祖先求的是兩點(diǎn)的最近的公共祖先。而祖先肯定是在兩者上面的翻擒，那這么說氓涣，祖先的深度是小的。那這樣就可以將RMQ與最近公共祖先聯(lián)系起來了陋气。但是要怎樣遍歷一棵樹才可以將它的深度分清楚呢劳吠。
先來操作一波

上面是什么遍歷呢」茫可以看出它是先根痒玩，再左再右。這樣能保證根一定在前面被遍歷。那這樣的話根的深度就比子節(jié)點(diǎn)小了蠢古。
還要注意奴曙，這個(gè)遍歷的特點(diǎn)哦！有回溯的過程哦草讶！保證根節(jié)點(diǎn)都在兩者之間洽糟。
分清遍歷序號和節(jié)點(diǎn)序號(如圖中的A，B......)哦!

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
using namespace std;
const int M=20010;
int n;
int head[M],cnt=0;
int vis[M],tot;//tot遍歷的序號
int depth[M],tra[M];//depth數(shù)組記錄每次遍歷的深度堕战，tra數(shù)組記錄的是遍歷的節(jié)點(diǎn)序號
int dp[M][25];//從第i個(gè)連續(xù)的2^j深度小的遍歷序號
int first[M];//記錄每個(gè)節(jié)點(diǎn)序號第一次出現(xiàn)的遍歷序號
struct node
{
    int v,nxt;
}edge[M];
void add(int x,int y)
{
    edge[++cnt].nxt=head[x];
    edge[cnt].v=y;
    head[x]=cnt;
}
void dfs(int x,int deth)
{
    vis[x]=1;
    tra[++tot]=x;//記錄節(jié)點(diǎn)序號
    depth[tot]=deth;//記錄每次遍歷序號對應(yīng)的深度
    first[x]=tot;//記錄節(jié)點(diǎn)序號第一次出現(xiàn)的遍歷序號tot
    for(int i=head[x];i!=-1;i=edge[i].nxt)
    {
        int u=edge[i].v;
        if(!vis[u])
        {
            dfs(u,deth+1);
            tra[++tot]=x;//遍歷回溯
            depth[tot]=deth;//每個(gè)遍歷序號的深度
        }
    }
}
int find(int x,int y)
{
    if(depth[x]<depth[y])//深度小的坤溃，返回遍歷序號
    {
        return x;
    }
    else
    {
        return y;
    }
    
}
void ST(int n)
{
    for(int i=1;i<=n;i++)
    {
        dp[i][0]=i;
    }
    for(int j=1;j<=24;j++)
    {
        for(int i=1;i+(1<<j)-1<=n;i++)
        {
            dp[i][j]=find(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
        }
    }
}
int RMQ(int i,int j)
{
    int k=log2(j-i+1.0);
    return find(dp[i][k],dp[j-(1<<k)+1][k]);
}
int LCA(int u,int v)
{
    int x=first[u];
    int y=first[v];
    if(x>y)
    {
        swap(x,y);
    }
    int res=RMQ(x,y);//得到了深度最小的遍歷序號了
    return tra[res];//返回節(jié)點(diǎn)序號
}
int main( )
{
    int t,n,x,y;
    cin>>t;
    while(t--)
    {
        tot=cnt=0;
        memset(head,-1,sizeof(head));
        memset(vis,0,sizeof(vis));
        cin>>n;
        for(int i=1;i<n;i++)
        {
            cin>>x>>y;
            add(x,y);
            vis[y]=1;
        }
        for(int i=1;i<=n;i++)
        {
            if(!vis[i])//尋找根節(jié)點(diǎn)開始遍歷
            {
                memset(vis,0,sizeof(vis));
                dfs(i,1);
                //cout<<i<<" i "<<endl;
                break;
            }
        }
        ST(2*n-1);
        // for(int i=1;i<=2*n-1;i++)
        // {
        //     cout<<tra[i]<<" ";
        // }
        //cout<<endl;
        cin>>x>>y;
        cout<<LCA(x,y)<<endl;
    }
    return 0;
}

倍增

倍增中的ST函數(shù)的意思是：在ST算法中，我們維護(hù)了一個(gè)數(shù)組 $DP[i][j]$ 嘱丢，表示的是以下標(biāo)為i為起點(diǎn)的長度為 $2^j$ 的序列的信息薪介。然后用動(dòng)態(tài)規(guī)劃的思想求出整個(gè)數(shù)組。剛才在上面說我們求LCA時(shí)一次要跳2的冪次方層屿讽，這就與DP數(shù)組中下標(biāo) $j$ 的定義不謀而合了。所以我們定義倍增法中的 $DP[i][j]$ 存放的是：結(jié)點(diǎn) $i$ 的向上 $2^j$ 層的祖先吠裆。例如下面這個(gè)圖：

$DP[4][1]=1$ 伐谈；結(jié)點(diǎn)4的向上 $2^1=2$ 層的祖先是結(jié)點(diǎn)1。
$DP[10][1]=2$ 试疙；結(jié)點(diǎn)10的向上 $2^1=2$ 層的祖先是結(jié)點(diǎn)2诵棵。
特別地， $DP[6][0]=3$ 祝旷，結(jié)點(diǎn)6的向上 $2^0=1$ 層的祖先是3履澳，即6的父節(jié)點(diǎn)。而這一現(xiàn)象正好可以當(dāng)做DP的初始條件怀跛。 $DP[i][0]$ 為 $i$ 的父節(jié)點(diǎn)距贷。下面寫出遞推式：
$DP[i][j] = DP[ DP[i][j-1] ] [j-1]$ ，如何理解這個(gè)遞推式呢吻谋？ $DP[i][j-1]$ 是結(jié)點(diǎn)i往上跳 $2^{(j-1)}$ 層的祖先忠蝗，那我們就在跳到這個(gè)結(jié)點(diǎn)的基礎(chǔ)上，再向上跳 $2^{(j-1)}$ 層漓拾，這樣就相當(dāng)于從結(jié)點(diǎn)i阁最，先跳 $2^{(j-1)}$ 層，跳到 $DP[i][j-1]$ 得到 $2^{(j-1)}$ 祖先節(jié)點(diǎn) $x$ ,節(jié)點(diǎn) $x$ （ $DP[i][j-1]$ ）再跳 $2^{(j-1)}$ 層骇两，最后還是到達(dá)了 $2^j$ 層
$DP[10][1]=DP[DP[10][1-1]][1-1]--->DP[5][0]-->2$ , $DP[10][0]$ 表示的是節(jié)點(diǎn)10跳1層到節(jié)點(diǎn)5速种，節(jié)點(diǎn)5在跳一層就不是節(jié)點(diǎn)10跳了2層了。低千。配阵。。。

再看這副圖：
$DP[15][0]=9;DP[15][1]=5;DP[15][2]=2;$
$DP[5][0]=4;DP[5][1]=2;$
$DP[15][2]=DP[DP[15][1]][1]=2$

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int deth[11000];
int dp[11000][25];
int vis[11000];
int head[11000];
int cnt;
struct node
{
    int v,nxt;
}edge[11000];
void add(int x,int y)
{
    edge[++cnt].nxt=head[x];
    edge[cnt].v=y;
    head[x]=cnt;
}
void dfs(int x,int u,int dep)
{
    dp[x][0]=u;
    deth[x]=dep;
    for(int i=head[x];i!=-1;i=edge[i].nxt)
    {
        int v=edge[i].v;
        dfs(v,x,dep+1);
    }
}
void Mul(int n)
{
    for(int j=1;(1<<j)<=n;j++)
    {
        for(int i=1;i<=n;i++)
        {
            dp[i][j]=dp[dp[i][j-1]][j-1];
        }
    }
}
int LCA(int x,int y)
{
    if(deth[x]<deth[y])//保證x的深度大
    {
        swap(x,y);
    }
    for(int i=24;i>=0;i--)
    {
        if(deth[x]-(1<<i)>=deth[y])//保證x的深度小于等于y闸餐，否則可能把最近公共祖先跳過了
        {
            x=dp[x][i];
        }
    }
    if(x==y)//兩者其中之一是對方的祖先
    {
        return x;
    }
    for(int i=24;i>=0;i--)//處于相同層饱亮，于是一直往上跳
    {
        if(dp[x][i]!=dp[y][i])//處于相同層，于是一直往上往下跳,直到兩者祖先不相同舍沙，開始分支x與y再向上跳
                             //如圖中的節(jié)點(diǎn)9與節(jié)點(diǎn)10近上，直到i=0時(shí)兩者才不相同，于是x=5,y=6拂铡，再返回x節(jié)點(diǎn)的1層祖先壹无。圖中的節(jié)點(diǎn)9與節(jié)點(diǎn)14，i=2時(shí)祖先相同感帅，但是i=1后面的不相同,于是x=4,y=7;i=0,但是4的1層祖先是2斗锭，7的1層祖先是3，所以x=2,y=3;返回節(jié)點(diǎn)2的1層祖先
        {
            x=dp[x][i];
            y=dp[y][i];
        }
    }
    return dp[x][0];//dp[y][0]
}
int main( )
{
    int t,n,x,y;
    cin>>t;
    while(t--)
    {
        cin>>n;
        cnt=0;
        memset(head,-1,sizeof(head));
        memset(vis,0,sizeof(vis));
        for(int i=1;i<n;i++)
        {
            cin>>x>>y;
            add(x,y);
            vis[y]=1;
        }
        for(int i=1;i<=n;i++)
        {
            if(vis[i]==0)
            {
                //cout<<i<<endl;
                dfs(i,-1,0);
                break;
            }
        }
        Mul(n);
        cin>>x>>y;
        cout<<LCA(x,y)<<endl;
    }
    return 0;
}

最后編輯于：2019.09.27 00:45:54

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者

人面猴
序言：七十年代末失球，一起剝皮案震驚了整個(gè)濱河市岖是，隨后出現(xiàn)的幾起案子，更是在濱河造成了極大的恐慌实苞，老刑警劉巖豺撑，帶你破解...
沈念sama閱讀 218,122評論 6贊 505
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件，死亡現(xiàn)場離奇詭異黔牵，居然都是意外死亡聪轿，警方通過查閱死者的電腦和手機(jī)，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 93,070評論 3贊 395
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門猾浦，熙熙樓的掌柜王于貴愁眉苦臉地迎上來陆错，“玉大人，你說我怎么就攤上這事金赦∫舸桑” “怎么了？”我有些...
開封第一講書人閱讀 164,491評論 0贊 354
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵夹抗，是天一觀的道長外莲。經(jīng)常有香客問我，道長兔朦，這世上最難降的妖魔是什么偷线？我笑而不...
開封第一講書人閱讀 58,636評論 1贊 293
?港島之戀（遺憾婚禮）
正文為了忘掉前任，我火速辦了婚禮沽甥，結(jié)果婚禮上声邦，老公的妹妹穿的比我還像新娘。我一直安慰自己摆舟，他們只是感情好亥曹，可當(dāng)我...
茶點(diǎn)故事閱讀 67,676評論 6贊 392
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布邓了。她就那樣靜靜地躺著，像睡著了一般媳瞪。火紅的嫁衣襯著肌膚如雪骗炉。梳的紋絲不亂的頭發(fā)上，一...
開封第一講書人閱讀 51,541評論 1贊 305
城市分裂傳說
那天蛇受，我揣著相機(jī)與錄音句葵，去河邊找鬼。笑死兢仰，一個(gè)胖子當(dāng)著我的面吹牛乍丈，可吹牛的內(nèi)容都是我干的。我是一名探鬼主播把将，決...
沈念sama閱讀 40,292評論 3贊 418
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼轻专，長吁一口氣：“原來是場噩夢啊……” “哼！你這毒婦竟也來了察蹲？” 一聲冷哼從身側(cè)響起请垛，我...
開封第一講書人閱讀 39,211評論 0贊 276
萬榮殺人案實(shí)錄
序言：老撾萬榮一對情侶失蹤，失蹤者是張志新（化名）和其女友劉穎洽议，沒想到半個(gè)月后宗收，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體，經(jīng)...
沈念sama閱讀 45,655評論 1贊 314
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡绞铃，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 37,846評論 3贊 336
?白月光啟示錄
正文我和宋清朗相戀三年镜雨，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了嫂侍。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片儿捧。...
茶點(diǎn)故事閱讀 39,965評論 1贊 348
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡，死狀恐怖挑宠，靈堂內(nèi)的尸體忽然破棺而出菲盾，到底是詐尸還是另有隱情，我是刑警寧澤各淀，帶...
沈念sama閱讀 35,684評論 5贊 347
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布懒鉴，位于F島的核電站，受9級特大地震影響碎浇，放射性物質(zhì)發(fā)生泄漏临谱。R本人自食惡果不足惜，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 41,295評論 3贊 329
男人毒藥：我在死后第九天來索命
文/蒙蒙一奴璃、第九天我趴在偏房一處隱蔽的房頂上張望悉默。院中可真熱鬧，春花似錦苟穆、人聲如沸抄课。這莊子的主人今日做“春日...
開封第一講書人閱讀 31,894評論 0贊 22
一樁弒父案，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽跟磨。三九已至间聊，卻和暖如春，著一層夾襖步出監(jiān)牢的瞬間抵拘，已是汗流浹背哎榴。一陣腳步聲響...
開封第一講書人閱讀 33,012評論 1贊 269
情欲美人皮
我被黑心中介騙來泰國打工，沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留仑濒，地道東北人叹话。一個(gè)月前我還...
沈念sama閱讀 48,126評論 3贊 370
代替公主和親
正文我出身青樓，卻偏偏與公主長得像墩瞳，于是被迫代替她去往敵國和親驼壶。傳聞我的和親對象是個(gè)殘疾皇子，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 44,914評論 2贊 355

最近公共祖先(LCA-tarjan/RMQ/倍增)

tarjan求LCA原理：

RMQ與LCA

倍增

推薦閱讀更多精彩內(nèi)容