LCA_最近公共祖先

　　LCA 最近公共祖先
　　在一棵沒有環(huán)的樹上，每個(gè)節(jié)點(diǎn)肯定有其父親節(jié)點(diǎn)和祖先節(jié)點(diǎn)震嫉，而最近公共祖先赤赊，就是兩個(gè)節(jié)點(diǎn)在這棵樹上深度最大的公共的祖先節(jié)點(diǎn)。
　　換句話說聚请，就是兩個(gè)點(diǎn)在這棵樹上距離最近的公共祖先節(jié)點(diǎn)荠雕。
　　對(duì)于一棵有權(quán)樹，假設(shè)u,v兩點(diǎn)的最近公共祖先lca(v),若dis[u]表示根節(jié)點(diǎn)到u的長(zhǎng)度驶赏，則uv間的距離為dis=dis[u]+dis[v]-2*dis[lca(v)]
有人可能會(huì)問：那他本身或者其父親節(jié)點(diǎn)是否可以作為祖先節(jié)點(diǎn)呢？
　　　　答案是肯定的既鞠，很簡(jiǎn)單煤傍，按照人的親戚觀念來說，你的父親也是你的祖先嘱蛋，而LCA還可以將自己視為祖先節(jié)點(diǎn)蚯姆。
　　　　舉個(gè)例子吧，如下圖所示４和５的最近公共祖先是２洒敏，５和３的最近公共祖先是１龄恋，２和１的最近公共祖先是１⌒谆铮　

求LCA主要有兩種方法:離線的DFS+并查集和在線的RMQ算法
　　這里簡(jiǎn)單說一說在線和離線的區(qū)別:在計(jì)算機(jī)科學(xué)中郭毕，一個(gè)在線算法是指它可以以序列化的方式一個(gè)個(gè)的處理輸入，也就是說在開始時(shí)并不需要已經(jīng)知道所有的輸入函荣。相對(duì)的显押，對(duì)于一個(gè)離線算法，在開始時(shí)就需要知道問題的所有輸入數(shù)據(jù)傻挂，而且在解決一個(gè)問題后就要立即輸出結(jié)果乘碑。

( 一 )離線算法:tarjan和并查集

Code From Wikipedia

 function TarjanOLCA(u)
     u.ancestor := u;
     for each v in u.children do
         TarjanOLCA(v);
         Union(u,v);
         Find(u).ancestor := u;
     u.color := black;
     for each v such that {u,v} in P do
         if v.color == black
             print "Tarjan's Lowest Common Ancestor of " + u +
                   " and " + v + " is " + Find(v).ancestor + ".";

其中,根節(jié)點(diǎn)是可以隨意選擇的

How far away ？
題意:
給定一棵帶權(quán)樹金拒，求u兽肤，v兩節(jié)點(diǎn)的路徑長(zhǎng)度
題解：
找到u,v兩點(diǎn)的最近公共祖先lca(v)
若dis[u]表示根節(jié)點(diǎn)到u的長(zhǎng)度，則dis=dis[u]+dis[v]-2*dis[lca(v)]

#include<cstdio>
#include <algorithm>
#include<cstring>
using namespace std;
const int MAXN=40010;
const int BLACK=1,WHITE=0;
int father[MAXN],vis[MAXN],dis[MAXN],color[MAXN];
int parent(int u)
{
    while(u!=father[u])
    {
        father[u]=father[father[u]];
        u=father[u];
    }
    return u;
}
void connect(int u,int v)//v作為u的兒子
{
    int fu=parent(u);
    int fv=parent(v);
    father[fv]=fu;
}
struct Node
{
    int to,next,val;
};
Node edge[MAXN<<1];
int head[MAXN],cnt;
void addEdge(int u,int v,int val)
{
    edge[cnt].to=v;
    edge[cnt].val=val;
    edge[cnt].next=head[u];
    head[u]=cnt++;
    edge[cnt].to=u;
    edge[cnt].val=val;
    edge[cnt].next=head[v];
    head[v]=cnt++;
}
struct Ask
{
    int u,to,next,lca;
};
Ask arr[MAXN<<1];
int ask_head[MAXN],idx;
void addAsk(int u,int v)
{
    arr[idx].u=u;arr[idx].to=v;arr[idx].next=ask_head[u];ask_head[u]=idx++;
    arr[idx].u=v;arr[idx].to=u;arr[idx].next=ask_head[v];ask_head[v]=idx++;
}
void tarjan(int u)
{
    vis[u]=1;
    for(int i=head[u];i!=-1;i=edge[i].next)
    {
        int v=edge[i].to;
        if(vis[v]==0)
        {
            dis[v]=dis[u]+edge[i].val;
            tarjan(v);
            connect(u,v);
        }
    }
    color[u]=BLACK;
    for(int i=ask_head[u];i!=-1;i=arr[i].next)
    {
        int v=arr[i].to;
        if(color[v]==BLACK)
        {
            int fa=parent(v);
            arr[i].lca=fa;
            arr[i^1].lca=fa;
        }
    }
}
int main()
{
    int t,n,m,u,v,val;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        memset(head,-1,sizeof(head));
        memset(ask_head,-1,sizeof(ask_head));
        memset(vis,0,sizeof(vis));
        memset(color,WHITE,sizeof(color));
        for(int i=1;i<=n;i++) father[i]=i;
        cnt=idx=0;
        for(int i=1;i<n;i++)
        {
            scanf("%d%d%d",&u,&v,&val);
            addEdge(u,v,val);
        }
        for(int i=0;i<m;i++)
        {
            scanf("%d%d",&u,&v);
            addAsk(u,v);
        }
        dis[1]=0;
        tarjan(1);
        for(int i=0;i<idx;i+=2)
        {
            printf("%d\n",dis[arr[i].u]+dis[arr[i].to]-2*dis[arr[i].lca]);
        }
    }
}

( 二 )在線算法: RMQ算法
一：LCA和RMQ是可以相互轉(zhuǎn)化的
LCA轉(zhuǎn)RMQ算法是一個(gè)在線算法：先用時(shí)間去做預(yù)處理，然后每讀入一個(gè)詢問资铡，就用很短的時(shí)間去回答它沉迹，即”問一個(gè)答一個(gè)，回答時(shí)間很短“
預(yù)備知識(shí)：LCA轉(zhuǎn)為RMQ后害驹，幾乎是裸的RMQ問題鞭呕，RMQ問題，這里推薦ST算法求解宛官，如果不懂ST算法葫松，先學(xué)習(xí)一下

RMQ算法求LCA的模板如下:

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=500010;
const int MAXE=500010;
struct Node
{
    int to,next,val;
};
Node edge[MAXE];
int head[MAXN],cnt;
void addEdge(int u,int v,int val)
{
    edge[cnt].to=v;
    edge[cnt].val=val;
    edge[cnt].next=head[u];
    head[u]=cnt++;
}
int sequence[MAXN*2];//保存遍歷的節(jié)點(diǎn)序列,長(zhǎng)度為2*n-1,從下標(biāo)1開始保存
int deep[MAXN*2];//和遍歷序列對(duì)應(yīng)的深度數(shù)組,長(zhǎng)度為2*n-1,從下標(biāo)1開始保存
int first[MAXN];//每個(gè)節(jié)點(diǎn)在遍歷序列時(shí)第一次出現(xiàn)的位置
int dis[MAXN];//每個(gè)節(jié)點(diǎn)到樹根的距離
int dp[MAXN*1][25];//Sparse_table
bool vis[MAXN];//DFS遍歷的訪問數(shù)組
int tot;//序列下標(biāo)記錄
void DFS(int u,int dep)
{
    vis[u]=1;
    sequence[++tot]=u;first[u]=tot;deep[tot]=dep;
    for(int i=head[u];i!=-1;i=edge[i].next)
    {
        int v=edge[i].to;
        if(vis[v]==0)
        {
            dis[v]=dis[u]+edge[i].val;
            DFS(v,dep+1);
            sequence[++tot]=u;
            deep[tot]=dep;
        }
    }
}
void ST(int len)//index from 1 - len
{
    for(int i=1;i<=len;i++) dp[i][0]=i;

    for(int j=1;(1<<j)<=len;j++)//(length)=j<<1
        for(int i=1;i+(1<<j)-1<=len;i++)
        {
            int a=dp[i][j-1],b=dp[i+(1<<(j-1))][j-1];
            if(deep[a]<deep[b]) dp[i][j]=a;
            else dp[i][j]=b;
        }
}
int RMQ(int x,int y)
{
    int k=0;
    while(1<<(k+1)<=y-x+1) k++;
    int a=dp[x][k],b=dp[y-(1<<k)+1][k];
    if(deep[a]<deep[b]) return a;
    else return b;
}
int LCA(int a,int b)
{
    int x=first[a],y=first[b];
    if(x>y) swap(x,y);
    return sequence[RMQ(x,y)];
}
int main()
{
    int t,n,m,u,v,val;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        memset(head,-1,sizeof(head));
        memset(vis,0,sizeof(vis));
        cnt=tot=0;
        for(int i=1;i<n;i++)
        {
            scanf("%d%d%d",&u,&v,&val);
            addEdge(u,v,val);
            addEdge(v,u,val);
        }
        dis[1]=0;
        DFS(1,1);
        ST(tot);
        for(int i=0;i<m;i++)
        {
            scanf("%d%d",&u,&v);
            printf("%d\n",dis[u]+dis[v]-2*dis[LCA(u,v)]);
        }
    }
}

類似的,這里給出帶有pos數(shù)組的RMQ算法

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=40010;
const int MAXE=MAXN*2;
struct Node
{
    int to,next,val;
};
Node edge[MAXE];
int head[MAXN],cnt;
void addEdge(int u,int v,int val)
{
    edge[cnt].to=v;
    edge[cnt].val=val;
    edge[cnt].next=head[u];
    head[u]=cnt++;
}
int sequence[MAXN*2];//保存遍歷的節(jié)點(diǎn)序列,長(zhǎng)度為2*n-1,從下標(biāo)1開始保存
int deep[MAXN*2];//和遍歷序列對(duì)應(yīng)的深度數(shù)組,長(zhǎng)度為2*n-1,從下標(biāo)1開始保存
int first[MAXN];//每個(gè)節(jié)點(diǎn)在遍歷序列時(shí)第一次出現(xiàn)的位置
int dis[MAXN];//每個(gè)節(jié)點(diǎn)到樹根的距離
int dp[MAXN*2][25];//Sparse_table
int pos[MAXN*2][25];
bool vis[MAXN];//DFS遍歷的訪問數(shù)組
int tot;//序列下標(biāo)記錄
int temp[MAXN*2];
void DFS(int u,int dep)
{
    vis[u]=1;
    sequence[++tot]=u;first[u]=tot;deep[tot]=dep;
    for(int i=head[u];i!=-1;i=edge[i].next)
    {
        int v=edge[i].to;
        if(vis[v]==0)
        {
            dis[v]=dis[u]+edge[i].val;
            DFS(v,dep+1);
            sequence[++tot]=u;
            deep[tot]=dep;
        }
    }
}
void ST(int len)//index from 1 - len
{
    for(int i=1;i<=len;i++) dp[i][0]=deep[i];
    for(int i=1;i<=len;i++) pos[i][0]=i;

    for(int j=1;(1<<j)<=len;j++)//(length)=j<<1
        for(int i=1;i+(1<<j)-1<=len;i++)
        {
            if(dp[i][j-1]<dp[i+(1<<(j-1))][j-1])
            {
                dp[i][j]=dp[i][j-1];
                pos[i][j]=pos[i][j-1];
            }
            else
            {
                dp[i][j]=dp[i+(1<<(j-1))][j-1];
                pos[i][j]=pos[i+(1<<(j-1))][j-1];
            }
        }
}
int RMQ(int x,int y)
{
    int k=0;
    while(1<<(k+1)<=y-x+1) k++;
    return dp[x][k]<dp[y-(1<<k)+1][k]?pos[x][k]:pos[y-(1<<k)+1][k];
}
int LCA(int a,int b)
{
    int x=first[a],y=first[b];
    if(x>y) swap(x,y);
    return sequence[RMQ(x,y)];
}
int main()
{
    int t,n,m,u,v,val;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        memset(head,-1,sizeof(head));
        memset(vis,0,sizeof(vis));
        cnt=tot=0;
        for(int i=1;i<n;i++)
        {
            scanf("%d%d%d",&u,&v,&val);
            addEdge(u,v,val);
            addEdge(v,u,val);
        }
        dis[1]=0;
        DFS(1,1);
        ST(tot);
        for(int i=0;i<m;i++)
        {
            scanf("%d%d",&u,&v);
            printf("%d\n",dis[u]+dis[v]-2*dis[LCA(u,v)]);
        }
    }
}

Design the city
題意:
求樹的三點(diǎn)距離
題解:
u,v,w三點(diǎn)距離其實(shí)等于(dis(u,v)+dis(u,w)+dis(v,w))/2;
方法一:離線算法:tarjan和并查集

#include<cstdio>
#include <algorithm>
#include<cstring>
using namespace std;
const int MAXN=50010;
const int BLACK=1,WHITE=0;
int father[MAXN],vis[MAXN],dis[MAXN],color[MAXN];
int parent(int u)
{
    while(u!=father[u])
    {
        father[u]=father[father[u]];
        u=father[u];
    }
    return u;
}
void connect(int u,int v)//v作為u的兒子
{
    int fu=parent(u);
    int fv=parent(v);
    father[fv]=fu;
}
struct Node
{
    int to,next,val;
};
Node edge[MAXN<<1];
int head[MAXN],cnt;
void addEdge(int u,int v,int val)
{
    edge[cnt].to=v;
    edge[cnt].val=val;
    edge[cnt].next=head[u];
    head[u]=cnt++;
    edge[cnt].to=u;
    edge[cnt].val=val;
    edge[cnt].next=head[v];
    head[v]=cnt++;
}
struct Ask
{
    int u,to,next,lca;
};
Ask arr[70010*6];
int ask_head[MAXN],idx;
void addAsk(int u,int v)
{
    arr[idx].u=u;arr[idx].to=v;arr[idx].next=ask_head[u];ask_head[u]=idx++;
    arr[idx].u=v;arr[idx].to=u;arr[idx].next=ask_head[v];ask_head[v]=idx++;
}
void tarjan(int u)
{
    vis[u]=1;
    for(int i=head[u];i!=-1;i=edge[i].next)
    {
        int v=edge[i].to;
        if(vis[v]==0)
        {
            dis[v]=dis[u]+edge[i].val;
            tarjan(v);
            connect(u,v);
        }
    }
    color[u]=BLACK;
    for(int i=ask_head[u];i!=-1;i=arr[i].next)
    {
        int v=arr[i].to;
        if(color[v]==BLACK)
        {
            int fa=parent(v);
            arr[i].lca=fa;
            arr[i^1].lca=fa;
        }
    }
}
int main()
{
    int t,n,m,u,v,w,val,cas=0;
    while(scanf("%d",&n)!=EOF)
    {
        if(cas++) printf("\n");
        memset(head,-1,sizeof(head));
        memset(ask_head,-1,sizeof(ask_head));
        memset(vis,0,sizeof(vis));
        memset(color,WHITE,sizeof(color));
        for(int i=1;i<=n;i++) father[i]=i;
        cnt=idx=0;
        for(int i=1;i<n;i++)
        {
            scanf("%d%d%d",&u,&v,&val);
            addEdge(u+1,v+1,val);
        }
        scanf("%d",&m);
        for(int i=0;i<m;i++)
        {
            scanf("%d%d%d",&u,&v,&w);
            addAsk(u+1,v+1);addAsk(u+1,w+1);addAsk(v+1,w+1);
        }
        dis[1]=0;
        tarjan(1);
        for(int i=0;i<idx;i+=6)
        {
            int d1=dis[arr[i].u]+dis[arr[i].to]-2*dis[arr[i].lca];
            int d2=dis[arr[i+2].u]+dis[arr[i+2].to]-2*dis[arr[i+2].lca];
            int d3=dis[arr[i+4].u]+dis[arr[i+4].to]-2*dis[arr[i+4].lca];
            printf("%d\n",(d1+d2+d3)/2);
        }
    }
}

方法二:在線算法: RMQ算法

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=50010;
const int MAXE=MAXN*2;
struct Node
{
    int to,next,val;
};
Node edge[MAXE];
int head[MAXN],cnt;
void addEdge(int u,int v,int val)
{
    edge[cnt].to=v;
    edge[cnt].val=val;
    edge[cnt].next=head[u];
    head[u]=cnt++;
}
int first[MAXN];
int vis[MAXN];
int deep[MAXN*2];
int sequence[MAXN*20];
int dis[MAXN];
int dp[MAXN*2][25];
int tot;
void DFS(int u,int dep)
{
    vis[u]=1;
    sequence[++tot]=u;deep[tot]=dep;first[u]=tot;
    for(int i=head[u];i!=-1;i=edge[i].next)
    {
        int v=edge[i].to;
        if(vis[v]==0)
        {
            dis[v]=dis[u]+edge[i].val;
            DFS(v,dep+1);
            sequence[++tot]=u;
            deep[tot]=dep;
        }
    }
}
void ST(int len)
{
    for(int i=1;i<=len;i++) dp[i][0]=i;
    for(int j=1;(1<<j)<=len;j++)
    {
        for(int i=1;i+(1<<j)-1<=len;i++)
        {
            int a=dp[i][j-1],b=dp[i+(1<<(j-1))][j-1];
            if(deep[a]<deep[b]) dp[i][j]=dp[i][j-1];
            else dp[i][j]=dp[i+(1<<(j-1))][j-1];
        }
    }
}
int RMQ(int x,int y)
{
    int k=0;
    while((1<<(k+1))<=y-x+1) k++;
    return deep[dp[x][k]]<deep[dp[y-(1<<k)+1][k]]?dp[x][k]:dp[y-(1<<k)+1][k];
}
int LCA(int u,int v)
{
    int x=first[u],y=first[v];
    if(x>y) swap(x,y);
    return sequence[RMQ(x,y)];
}
int main()
{
    int n,m,u,v,val,a,b,c;
    bool start=true;
    while(scanf("%d",&n)!=EOF)
    {
        if(!start) printf("\n");
        memset(head,-1,sizeof(head));
        memset(vis,0,sizeof(vis));
        cnt=tot=0;
        for(int i=1;i<n;i++)
        {
            scanf("%d%d%d",&u,&v,&val);
            addEdge(u+1,v+1,val);
            addEdge(v+1,u+1,val);
        }
        dis[1]=0;
        DFS(1,1);
        ST(tot);
        scanf("%d",&m);
        while(m--)
        {
            scanf("%d%d%d",&a,&b,&c);
            a++;b++;c++;
            int d1=dis[a]+dis[b]-2*dis[LCA(a,b)];
            int d2=dis[a]+dis[c]-2*dis[LCA(a,c)];
            int d3=dis[b]+dis[c]-2*dis[LCA(b,c)];
            printf("%d\n",(d1+d2+d3)/2);
        }
        start=false;
    }
}

最后編輯于：2017.12.10 01:00:01

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

人面猴
序言：七十年代末，一起剝皮案震驚了整個(gè)濱河市底洗，隨后出現(xiàn)的幾起案子腋么，更是在濱河造成了極大的恐慌，老刑警劉巖亥揖，帶你破解...
沈念sama閱讀 221,430評(píng)論 6贊 515
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件珊擂，死亡現(xiàn)場(chǎng)離奇詭異，居然都是意外死亡费变，警方通過查閱死者的電腦和手機(jī)摧扇，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 94,406評(píng)論 3贊 398
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來挚歧，“玉大人扛稽，你說我怎么就攤上這事』海” “怎么了在张？”我有些...
開封第一講書人閱讀 167,834評(píng)論 0贊 360
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵，是天一觀的道長(zhǎng)矮慕。經(jīng)常有香客問我帮匾，道長(zhǎng)，這世上最難降的妖魔是什么痴鳄？我笑而不...
開封第一講書人閱讀 59,543評(píng)論 1贊 296
?港島之戀（遺憾婚禮）
正文為了忘掉前任瘟斜，我火速辦了婚禮，結(jié)果婚禮上夏跷，老公的妹妹穿的比我還像新娘哼转。我一直安慰自己，他們只是感情好槽华，可當(dāng)我...
茶點(diǎn)故事閱讀 68,547評(píng)論 6贊 397
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布壹蔓。她就那樣靜靜地躺著，像睡著了一般猫态。火紅的嫁衣襯著肌膚如雪佣蓉。梳的紋絲不亂的頭發(fā)上披摄，一...
開封第一講書人閱讀 52,196評(píng)論 1贊 308
城市分裂傳說
那天，我揣著相機(jī)與錄音勇凭，去河邊找鬼疚膊。笑死，一個(gè)胖子當(dāng)著我的面吹牛虾标，可吹牛的內(nèi)容都是我干的寓盗。我是一名探鬼主播，決...
沈念sama閱讀 40,776評(píng)論 3贊 421
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼璧函，長(zhǎng)吁一口氣：“原來是場(chǎng)噩夢(mèng)啊……” “哼傀蚌！你這毒婦竟也來了？” 一聲冷哼從身側(cè)響起蘸吓，我...
開封第一講書人閱讀 39,671評(píng)論 0贊 276
萬榮殺人案實(shí)錄
序言：老撾萬榮一對(duì)情侶失蹤善炫，失蹤者是張志新（化名）和其女友劉穎，沒想到半個(gè)月后库继，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體箩艺，經(jīng)...
沈念sama閱讀 46,221評(píng)論 1贊 320
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 38,303評(píng)論 3贊 340
?白月光啟示錄
正文我和宋清朗相戀三年宪萄，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了艺谆。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
茶點(diǎn)故事閱讀 40,444評(píng)論 1贊 352
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡雨膨，死狀恐怖擂涛，靈堂內(nèi)的尸體忽然破棺而出，到底是詐尸還是另有隱情聊记，我是刑警寧澤，帶...
沈念sama閱讀 36,134評(píng)論 5贊 350
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布恢暖，位于F島的核電站排监，受9級(jí)特大地震影響，放射性物質(zhì)發(fā)生泄漏杰捂。R本人自食惡果不足惜舆床，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 41,810評(píng)論 3贊 333
男人毒藥：我在死后第九天來索命
文/蒙蒙一、第九天我趴在偏房一處隱蔽的房頂上張望嫁佳。院中可真熱鬧挨队，春花似錦、人聲如沸蒿往。這莊子的主人今日做“春日...
開封第一講書人閱讀 32,285評(píng)論 0贊 24
一樁弒父案，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽瓤漏。三九已至腾夯，卻和暖如春颊埃，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背蝶俱。一陣腳步聲響...
開封第一講書人閱讀 33,399評(píng)論 1贊 272
情欲美人皮
我被黑心中介騙來泰國(guó)打工班利，沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留，地道東北人榨呆。一個(gè)月前我還...
沈念sama閱讀 48,837評(píng)論 3贊 376
代替公主和親
正文我出身青樓罗标，卻偏偏與公主長(zhǎng)得像，于是被迫代替她去往敵國(guó)和親积蜻。傳聞我的和親對(duì)象是個(gè)殘疾皇子闯割，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 45,455評(píng)論 2贊 359

LCA_最近公共祖先

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