一、什么是LCA?

??????LCA：Least Common Ancestors（最近公共祖先），對于一棵有根樹T的任意兩個節點u，v，求出LCA(T, u, v)，即離跟最遠的節點x，使得x同時是u和v的祖先。

二、算法分類

　　求LCA的算法很多，按照是否在線可以分為在線算法和離線算法。
??????在線算法：用比較長的時間做預處理，但是等信息充足以后每次回答詢問只需要用比較少的時間。
??????離線算法：先把所有的詢問讀入，然后一起把所有詢問回答完成，不是本文所講，Click here

三、在線算法

　　(1)什么是RMQ?

　　RMQ：給出一個數組A，回答詢問RMQ(A, i, j)，即A[i...j]之間的最值的下標。

　　(2)RMQ算法，不是本文所講，Click here

　　(3)RMQ與LCA?

　　假設一顆有根樹，如圖所示：

　　

　　我們可以通過深搜（從1節點開始）得到這樣一個序列：

　　歐拉序列V：1 2 1 3 4 3 5 6 5 7 5 3 1

　　深度序列D：0 1 0 1 2 1 2 3 2 3 2 1 0

　　First：1 2 4 5 7 8 10

　　First表示節點i在歐拉序列V中第一次出現的位置

　　

　　現在比如我們要求LCA(4，7)

　　那么找到節點4和7第一次出現的位置即：First(4)=5,First(7)=10

　　對應到歐拉序列V中區間[5,10]即：4 3 5 6 5 7

　　發現正好是以3為根的子樹，然我我們找到這幾個數中深度最小的即D(3)，說明3就是4和7的最近公共祖先

?

　　同理再比如說要求LCA(2,5)，First(2)=2，First(5)=7，找到對應區間[2,7]即2 1 3 4 3 5

　　然后找到深度最小的即1，說明1就是2和5的最近公共祖先。

四：例題

　　HDU 2586

?

　　AC CODE：

　　

#include <iostream> #include <cstdio> #include <cstring> #include <cmath> using namespace std; #define min(a,b) ((a)<(b)?(a):(b)) #define N 40010 #define M N*2struct edge {int u,v,w,next; }edge[M]; int tot,head[N];int n,m; int idx; bool vis[N]; int ver[2*N]; int dep[2*N]; int first[N]; int dis[N]; int dp[2*N][20];void init() {tot=0;memset(head,-1,sizeof(head)); } void add(int u,int v,int w) {edge[tot].u=u;edge[tot].v=v;edge[tot].w=w;edge[tot].next=head[u];head[u]=tot++; } void init2() {idx=0;dis[1]=0;memset(vis,0,sizeof(vis)); } void dfs(int u,int d) {vis[u]=1;ver[++idx]=u;first[u]=idx;dep[idx]=d;for(int i=head[u];i!=-1;i=edge[i].next){int v=edge[i].v;if(!vis[v]){int w=edge[i].w;dis[v]=dis[u]+w;dfs(v,d+1);ver[++idx]=u;dep[idx]=d;}} } void ST(int n) {int i,j;for(i=1;i<=n;i++) dp[i][0]=i;for(j=1;(1<<j)<=n;j++){for(i=1;i<=n;i++){if(i+(1<<j)-1<=n){int a=dp[i][j-1];int b=dp[i+(1<<(j-1))][j-1];dp[i][j]=dep[a]<dep[b]?a:b;}}} } int RMQ(int i,int j) {int k=(int)(log((double)(j-i+1))/log(2.0));int a=dp[i][k],b=dp[j-(1<<k)+1][k];return dep[a]<dep[b]?a:b; } 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 ver[res]; } int main() {int T;scanf("%d",&T);while(T--){init();scanf("%d%d",&n,&m);for(int i=1;i<n;i++){int u,v,w;scanf("%d%d%d",&u,&v,&w);add(u,v,w);add(v,u,w);}init2();dfs(1,0);ST(2*n-1);while(m--){int u,v;scanf("%d%d",&u,&v);int lca=LCA(u,v);printf("%d\n",dis[u]+dis[v]-2*dis[lca]);}}return 0; }

?

轉載于:https://www.cnblogs.com/hate13/p/4584531.html

總結

以上是生活随笔為你收集整理的LCA与RMQ的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。