poj1330Nearest Common Ancestors(LCA小結)

題目請戳這裡

題目大意：意如其名。

題目分析：本題隻有一個查詢，是以可以各種亂搞過去。

不過對于菜鳥而言，還是老老實實練習一下LCA算法。

LCA有很多經典的算法。按工作方式分線上和離線2種。

tarjan算法是經典的離線算法。這篇部落格講的太好懂了，我也不好意思班門弄斧，具體戳進去看看就會明白。重點是那個插圖，一看秒懂。

線上算法主要有倍增算法和轉RMQ算法。

另外LCA還有2種更為高效的O(n)-O(1)算法。一種請戳這裡，另一種其實就是先将LCA轉化成RMQ，再利用笛卡爾樹O（n）預處理，O（1）回答，具體可以戳這裡。

後兩種O(n)算法還沒有仔細研究，大緻看了下，不是很明白，但是感覺很厲害的樣子。mark一下，以後抽時間學習一下。

下面給出本題的前3種算法具體實作：

1：tarjan算法（雖然對本題來說有點奢侈了。。）

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 10005;
struct node
{
    int to,next;
}e[N];
int head[N],set[N],fa[N],in[N];
bool vis[N];
int n,num,p,q;
void build(int s,int ed)
{
    e[num].to = ed;
    e[num].next = head[s];
    head[s] = num ++;
}
void init()
{
    num = 0;
    memset(head,-1,sizeof(head));
    memset(in,0,sizeof(in));
}
int find(int x)
{
    int rt = x;
    while(set[rt] != rt)
        rt = set[rt];
    int pa = set[x];
    while(pa != rt)
    {
        set[x] = rt;
        x  = pa;
        pa = set[x];
    }
    return rt;
}
void bing(int a,int b)
{
    int ra = find(a);
    int rb = find(b);
    if(ra != rb)
        set[rb] = ra;
}
void dfs(int cur)
{
    fa[cur] = cur;
    set[cur] = cur;
    int i;
    for(i = head[cur];i != -1;i = e[i].next)
    {
        dfs(e[i].to);
        bing(cur,e[i].to);
        fa[find(cur)] = cur;
    }
    vis[cur] = true;
    if((p == cur && vis[q]))
        printf("%d\n",fa[find(q)]);
    if((q == cur && vis[p]))
        printf("%d\n",fa[find(p)]);
}
void tarjan()
{
    int i;
    memset(vis,false,sizeof(vis));
    for(i = 1;i <= n;i ++)
        if(in[i] == 0)
            break;
    dfs(i);
}
int main()
{
    int t;
    int i,a,b;
    scanf("%d",&t);
    while(t --)
    {
        scanf("%d",&n);
        init();
        for(i = 1;i < n;i ++)
        {
            scanf("%d%d",&a,&b);
            build(a,b);
            in[b] ++;
        }
        scanf("%d%d",&p,&q);
        tarjan();
    }
    return 0;
}
           

2：LCA轉RMQ，再st算法：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int N = 20005;

int dep[N],pos[N],seq[N],first[N],in[N];
int dp[N][20];
struct node
{
    int to,next;
}e[N];
int head[N];
int n,num,p,q,id;
void build(int s,int ed)
{
    e[num].to = ed;
    e[num].next = head[s];
    head[s] = num ++;
}

void dfs(int cur,int deep)
{
    dep[cur] = deep;
    first[cur] = id;
    pos[id] = cur;
    seq[id ++] = dep[cur];
    int i;
    for(i = head[cur];i != -1;i = e[i].next)
    {
        dfs(e[i].to,deep + 1);
        pos[id] = cur;
        seq[id ++] = dep[cur];
    }
}
int rmq()
{
    int i,j;
    for(i = 1;i <= id;i ++)
        dp[i][0] = i;
    for(j = 1;(1<<j) <= id;j ++)
    {
        for(i = 1;(i + (1<<(j - 1))) <= id;i ++)
            if(seq[dp[i][j - 1]] < seq[dp[i + (1<<(j - 1))][j - 1]])
                dp[i][j] = dp[i][j - 1];
            else
                dp[i][j] = dp[i + (1<<(j - 1))][j - 1];
    }
    int tp = first[p];
    int tq = first[q];
    if(tp > tq)
        swap(tp,tq);
    int k = floor(log((double)(tq - tp + 1))/log(2.0));
    int tmp;
    if(seq[dp[tp][k]] < seq[dp[tq - (1<<k) + 1][k]])
        tmp = dp[tp][k];
    else
        tmp = dp[tq - (1<<k) + 1][k];
    return pos[tmp];
}
void solve()
{
    int i;
    id = 1;
    for(i = 1;i <= n;i ++)
        if(in[i] == 0)
            break;
    dfs(i,0);
    id --;
    printf("%d\n",rmq());
}
int main()
{
    int i,a,b,t;
    freopen("in.txt","r",stdin);
    scanf("%d",&t);
    while(t --)
    {
        scanf("%d",&n);
        num = 0;
        memset(head,-1,sizeof(head));
        memset(in,0,sizeof(in));
        for(i = 1;i < n;i ++)
        {
            scanf("%d%d",&a,&b);
            build(a,b);
            in[b] ++;
        }
        scanf("%d%d",&p,&q);
        solve();
    }
    return 0;
}
           

3：倍增算法：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 10005;

int dp[N][20],deep[N];
struct node
{
    int to,next;
}e[N];
int n,num,p,q;
int head[N],in[N];
void build(int s,int ed)
{
    e[num].to = ed;
    e[num].next = head[s];
    head[s] = num ++;
}
void dfs(int cur,int fa)
{
    deep[cur] = deep[fa] + 1;
    dp[cur][0] = fa;
    int i;
    for(i = 1;i < 18;i ++)
        dp[cur][i] = dp[dp[cur][i - 1]][i - 1];
    for(i = head[cur];i != -1;i = e[i].next)
    {
        dfs(e[i].to,cur);
    }
}
int lca()
{
    if(deep[p] < deep[q])
        swap(p,q);
    int i,j;
    for(j = deep[p] - deep[q],i = 0;j;j >>= 1,i ++)
    {
        if(j&1)
            p = dp[p][i];
    }
    if(p == q)
        return q;
    for(i = 18;i >= 0;i --)
    {
        if(dp[p][i] != dp[q][i])
        {
            p = dp[p][i];
            q = dp[q][i];
        }
    }
    return dp[q][0];
}
void solve()
{
    int i;
    memset(deep,0,sizeof(deep));
    for(i = 1;i <= n;i ++)
        if(in[i] == 0)
            break;
    dfs(i,0);
    printf("%d\n",lca());
}
int main()
{
    int t,i,a,b;
    freopen("in.txt","r",stdin);
    scanf("%d",&t);
    while(t --)
    {
        scanf("%d",&n);
        num = 0;
        memset(head,-1,sizeof(head));
        memset(in,0,sizeof(in));
        for(i = 1;i < n;i ++)
        {
            scanf("%d%d",&a,&b);
            build(a,b);
            in[b] ++;
        }
        scanf("%d%d",&p,&q);
        solve();
    }
    return 0;
}