樹上兩點的最近公共祖先（lca）

LCA(Least Common Ancestors)問題是指對于有根樹T的兩個節點u,v，最近公共祖先LCA(T,u,v)表示一個節點x，滿足x是u,v的祖先且x的深度盡可能大。對于x點來說，有一點非常特殊，那就是從u到v的路徑一定經過x。

對于LCA問題，一共有三種解法：1.離線算法Tarjan-LCA算法 2.線上算法，基于RMQ的算法 3.基于二分搜尋的算法，也稱為倍增算法

以傳送門為例

1.離線算法Tarjan-LCA算法

Tarjan算法基于深度優先搜尋的架構，對于新搜尋到的一個節點，首先建立由這個節點構成的集合，再對目前節點的每個子樹進行搜尋，每搜尋完一棵子樹，則可确定子樹内的LCA詢問都已經解決（詢問的兩個點都在這個子樹中）。其他的LCA詢問的結果必然在這個子樹之外（詢問的一個點不在這個子樹中），這時把子樹所形成的集合與目前節點的集合合并，并将目前節點設為這個集合的祖先。之後繼續搜尋下一棵子樹，直到目前節點的所有子樹搜尋完。這時把目前節點也設為已被檢查過的，同時可以處理有關目前節點的LCA詢問，如果有一個從目前節點到節點v的詢問，且v已被檢查過，則由于進行的是深度優先搜尋，目前節點與v的最近公共祖先一定還沒有被檢查，而這個最近公共祖先的包含v的子樹一定已經搜尋過了，那麼這個最近公共祖先一定是v所在集合的祖先。

對于每一點u：

(1).建立以u為代表元素的集合

(2).周遊與u相連的節點v，如果沒有被通路過，對于v使用Tarjan-LCA算法，結束後，将v的集合并入u的集合

(3).對于與u有關的詢問(u,v)，如果v被通路過，則結果就是v所在集合的代表元素

算法複雜度分析：由于深度優先搜尋會周遊到每條邊，也就是說深度優先搜尋的時間複雜度是O(m)。而對于每個詢問都要應答，每個應答在兩個點都被搜尋到之後應答，也就是說每個詢問應答一次，路徑壓縮後的并查集的查詢效率可以認為是O(1)，是以應答的時間效率為O(q)，總體時間效率為O(m+q)。而在樹上，m=n-1，也就是時間複雜度為O(n+q)，可以說是非常高效的。算法的缺點在于需要記錄所有的詢問後再應答，是離線的算法。

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

const int N=40010;
const int M=210;

struct edge{
    int u,v,w,next;
};
edge edges[2*N];
int head[N];

struct ask{
    int u,v,lca,next;
};
ask question[2*M];
int _head[N];

int tot,fa[N],vis[N],dir[N];

inline void add_edge(int u,int v,int w)
{
    edges[tot].u=u;
    edges[tot].v=v;
    edges[tot].w=w;
    edges[tot].next=head[u];
    head[u]=tot++;
    swap(u,v);
    edges[tot].u=u;
    edges[tot].v=v;
    edges[tot].w=w;
    edges[tot].next=head[u];
    head[u]=tot++;
}

inline void add_ask(int u,int v)
{
    question[tot].u=u;
    question[tot].v=v;
    question[tot].lca=-1;
    question[tot].next=_head[u];
    _head[u]=tot++;
    swap(u,v);
    question[tot].u=u;
    question[tot].v=v;
    question[tot].lca=-1;
    question[tot].next=_head[u];
    _head[u]=tot++;
}

int find(int u)
{
    if(fa[u]==u){
        return u;
    }else{
        return fa[u]=find(fa[u]);
    }
}

void tarjan(int u)
{
    vis[u]=true;
    fa[u]=u;
    for(int k=head[u];k!=-1;k=edges[k].next){
        if(!vis[edges[k].v]){
            int v=edges[k].v,w=edges[k].w;
            dir[v]=dir[u]+w;
            tarjan(v);
            fa[v]=fa[u];
        }
    }
    for(int k=_head[u];k!=-1;k=question[k].next){
        if(vis[question[k].v]){
            int v=question[k].v;
            question[k].lca=question[k^1].lca=find(v);
        }
    }
}

int main()
{
    int casen,n,q;
    scanf("%d",&casen);
    while(casen--){
        scanf("%d%d",&n,&q);
        memset(head,-1,sizeof(head));
        memset(_head,-1,sizeof(_head));
        tot=0;
        for(int i=1;i<n;i++){
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            add_edge(u,v,w);
        }
        tot=0;
        for(int i=1;i<=q;i++){
            int u,v;
            scanf("%d%d",&u,&v);
            add_ask(u,v);
        }
        memset(vis,0,sizeof(vis));
        dir[1]=0;
        tarjan(1);
        for(int i=0;i<q;i++){
            int s=2*i;
            int u=question[s].u;
            int v=question[s].v;
            int lca=question[s].lca;
            printf("%d\n",dir[u]+dir[v]-2*dir[lca]);
        }
    }
    return 0;
}
           

2.線上算法，基于RMQ的算法（了解DFS序傳送門）

對于涉及到有根樹的問題，将樹轉化成從根DFS标号後得到的序列處理的技巧十分有效。對于LCA，利用該技巧也能夠高效求解。首先，将從根DFS通路的順序得到的頂點序号vs[i]和對應的深度depth[i]。對于每個頂點v，記其在vs中首次出現的下标為id[v]。

這些都可以在O(n)時間内求得，而LCA(u,v)就是通路u之後到通路v之前所經過頂點中離根最近的那個，假設id[u]<=id[v]，那麼有

LCA(u,v)=vs[id[u]<=i<=id[v]中令depth(i)最小的i]

這些可以利用RMQ高效求得

算法複雜度分析：通過O(n)的處理轉化成RMQ問題，在O(nlogn)的時間内做預處理後形成線上的算法

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>

using namespace std;

const int N=40010;
const int M=25;

struct edge{
    int u,v,w,next;
};
edge edges[2*N];
int head[N];

int tot,vs[2*N],depth[2*N],first[N],dir[N],_pow[M];
bool vis[N];
int dp[2*N][M];

inline void add(int u,int v,int w)
{
    edges[tot].u=u;
    edges[tot].v=v;
    edges[tot].w=w;
    edges[tot].next=head[u];
    head[u]=tot++;
    swap(u,v);
    edges[tot].u=u;
    edges[tot].v=v;
    edges[tot].w=w;
    edges[tot].next=head[u];
    head[u]=tot++;
}

void dfs(int u,int dep)
{
    vis[u]=true;
    vs[++tot]=u;
    first[u]=tot;
    depth[tot]=dep;
    for(int k=head[u];k!=-1;k=edges[k].next){
        if(!vis[edges[k].v]){
            int v=edges[k].v,w=edges[k].w;
            dir[v]=dir[u]+w;
            dfs(v,dep+1);
            vs[++tot]=u;
            depth[tot]=dep;
        }
    }
}

void st(int len)
{
    int k=(int)(log((double)len)/log(2.0));
    for(int i=1;i<=len;i++){
        dp[i][0]=i;
    }
    for(int j=1;j<=k;j++){
        for(int i=1;i+_pow[j]-1<=len;i++){
            int a=dp[i][j-1],b=dp[i+_pow[j-1]][j-1];
            if(depth[a]<depth[b]){
                dp[i][j]=a;
            }else{
                dp[i][j]=b;
            }
        }
    }
}

int rmq(int x,int y)
{
    int k=(int)(log((double)(y-x+1))/log(2.0));
    int a=dp[x][k],b=dp[y-_pow[k]+1][k];
    if(depth[a]<depth[b]){
        return a;
    }else{
        return b;
    }
}

int lca(int u,int v)
{
    int x=first[u],y=first[v];
    if(x>y){
        swap(x,y);
    }
    int res=rmq(x,y);
    return vs[res];
}

int main()
{
    for(int i=0;i<M;i++){
        _pow[i]=(1<<i);
    }
    int casen;
    scanf("%d",&casen);
    while(casen--){
        int n,q;
        tot=0;
        scanf("%d%d",&n,&q);
        memset(head,-1,sizeof(head));
        for(int i=1;i<n;i++){
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            add(u,v,w);
        }
        tot=0;
        dir[1]=0;
        memset(vis,false,sizeof(vis));
        dfs(1,1);
        st(2*n-1);
        while(q--){
            int u,v;
            scanf("%d%d",&u,&v);
            int lcaa=lca(u,v);
            printf("%d\n",dir[u]+dir[v]-2*dir[lcaa]);
        }
    }
    return 0;
}
           

3.基于二分搜尋的算法，也成為倍增算法

設節點v到根的深度為depth(v)。那麼，如果節點w是u和v的公共祖先的話，讓u向上走depth(u)-depth(w)步，讓v向上走depth(v)-depth(w)步，都将走到w。是以，首先讓u和v中較深的一方向上走|depth(u)-depth(v)|步，再一步一步向上走，直到走到同一個節點，就可以在O(depth(u)+depth(v))時間内求出LCA。

vector<int>G[max_v];//圖的鄰接表表示
int root;

int parent[max_v];
int depth[max_v];

void dfs(int v,int p,int d)
{
    parent[v]=p;
    depth[v]=d;
    for(int i=0;i<G[v].size();i++){
        if(G[v][i!=p]){
            dfs(G[v][i],v,d+1);
        }
    }
}

void init()
{
    dfs(root,-1,0);
}

int lca(int u,int v)
{
    //讓u和v走到同一深度
    while(depth[u]>depth[v]){
        u=parent[u];
    }
    while(depth[v]>depth[u]){
        v=parent[v];
    }
    //讓u和v走到同一節點
    while(u!=v){
        u=parent[u];
        v=parent[v];
    }
    return u;
}
           

節點的最大深度是O(n)，是以該算法的複雜度也是O(n)。如果隻需要計算一次LCA的話，這便足夠了。但如果計算多對點的LCA的話就不行了，剛才的算法，通過不斷向上走到同一節點來計算u和v的LCA。這裡，到達了同一節點後，不論怎麼向上走，到達的顯然還是同一節點。利用這一點，我們使用二分搜尋求出到達共同祖先所需的最小步數嗎？事實上，隻要利用如下預處理，就可以實作二分搜尋。

首先，對于任意頂點v，利用其父親節點資訊，可以通過parent2[v]=parent[parent[v]]得到其向上走兩步所到的頂點。再利用這一資訊，又可以通過parent4[v]=parent2[parent2[v]]得到其向上走四步所到的頂點。依此類推，就能夠得到其向上走2^k步所到的頂點parent[k][v]。有了k=floor(logn)以内的所有資訊後，就可以進行二分搜尋了，每次的複雜度是O(logn)。另外，預處理parent[k][v]的複雜度是O(nlogn)。

vector<int>G[max_v];
int root;

int parent[max_log_v][max_v];
int depth[max_v];

void dfs(int v,int p;int d)
{
    parent[0][v]=p;
    depth[v]=d;
    for(int i=;i<G[v].size();i++){
        if(G[v][i]!=p){
            dfs(G[v][i],v,d+1);
        }
    }
}

void init(int V)
{
    dfs(root,-1,0);
    for(int k=0;k+1<max_log_v;k++){
        for(int v=0;v<V;v++){
            if(parent[k][v]<0){
                parent[k+1][v]=-1;
            }else{
                parent[k+1][v]=parent[k][parent[k][v]];
            }
        }
    }
}

int lca(int u,int v)
{
    if(depth[u]>depth[v]){
        swap(u,v);
    }
    for(int k=0;k<max_log_v;k++){
        if((depth[v]-depth[u])>>k&1){
            v=parent[k][v];
        }
    }
    if(u==v){
        return u;
    }
    for(int k=max_log_v-1;k>=0;k--){
        if(parent[k][u]!=parent[k][v]){
            u=parent[k][u];
            v=parent[k][v];
        }
    }
    return parent[0][u];
}