参考资料：

　　[1]:挑战程序设计竞赛

　　[2]:

　　[3]: [提取码：qvx1]

 

一、浅谈LCA

　　1.何为LCA

　　　　在有根树中，两个节点u和v的公共祖先中距离根节点最远的的那个被称为最近公共祖先(LCA,Lowest Common Ancestor)。

　　　　例如：

　　　   　　　

　　　　　　LCA(4,5) = 2;

　　　　　　LCA(4,3) = 1;

　　　　　　LCA(2,5) = 2;

　　2.高效计算LCA的算法

1. 基于二分的LCA
2. 基于Tarjan的LCA
3. 基于RMQ的LCA　　

二、浅谈高效算法

　　1.基于二分的LCA

　　　　(1)算法介绍：

　　　　　　详情请看挑战程序设计竞赛p328

　　　　(2)相关变量解释：

　　　　　　maxn;.....................................................最大的节点个数

　　　　　　root=1;...................................................人为规定1为根节点

　　　　　　depth[maxn];..........................................某节点的深度，根节点深度为0

　　　　　　dist[maxn];.............................................某节点距根节点的距离

　　　　　　fa[20][maxn];..........................................fa[ i ][ j ] : 记录节点 j 沿着其父结点 向上走 2^i 步所到的节点 （超过根节点时记为-1）

　　　　　　存图可以用邻接表(vector)或链式前向星（我比较倾向于链式前向星）

　　　　(3)算法模板

1 struct LCA 2 { 3     int fa[20][maxn]; 4     int dist[maxn]; 5     int depth[maxn]; 6     //一次DFS()预处理出fa[0][u],depth[u],dist[u] 7     void DFS(int u,int f,int dis,int dep) 8     { 9         fa[0][u]=f;//节点u向上走2^0步来到的节点便是其父节点10         dist[u]=dis;11         depth[u]=dep;12         for(int i=head[u];~i;i=G[i].next)13         {14             int v=G[i].to;15             int w=G[i].w;16             if(v != f)17                 DFS(v,u,dis+w,dep+1);18         }19     }20     void Preset()//预处理出 fa[20][maxn]，关键所在21     {22         DFS(1,-1,0,0);23         for(int i=0;i+1 < 20;++i)24             for(int u=1;u <= n;++u)25                 if(fa[i][u] == -1)26                     fa[i+1][u]=-1;27                 else28                     fa[i+1][u]=fa[i][fa[i][u]];29     }30     int lca(int u,int v)//返回u,v的最近公共祖先31     {32         if(depth[u] > depth[v])33             swap(u,v);34         for(int i=0;i < 20;++i)35             if((depth[v]-depth[u])>>i&1)36                 v=fa[i][v];37         if(u == v)38             return u;39         for(int k=19;k >= 0;--k)40             if(fa[k][u] != fa[k][v])41             {42                 u=fa[k][u];43                 v=fa[k][v];44             }45         return fa[0][u];46     }47 }_lca;

　　　　对第35，36行的理解：

　　　　假设 v 向上走 2^x₁,2^x₂,2^x₃,....,2^x_n 使得v节点来到u节点同深度的祖先节点；

　　　　即 depth[v]-depth[u] = 2^x₁+2^x₂+2^x₃+....+2^x_n;

　　　　令 d = depth[v]-depth[u]，那么 d / 2^x₁ , d / 2^x₂ , d / 2^x₃ ,...., d / 2^x_n 为奇数；

　　　　具体请详见我的这篇博客?

　　　　上述代码中的34，35，36查找v节点与u节点同一深度的祖先节点时可以优化一下（有些题因为这么一个小小的优化就过了，不然，TLE）

1 int i;2 for(i=0;(1<
     
      <= depth[v];++i);3 i--;//从根结点(depth[root]=0)向下走，最靠近且不会超过节点v的最大步数为2^i4 for(int k=i;k >= 0;--k)//求两者差值最少有多少个2的幂组成5     if((depth[v]-(1<
      
       = depth[u])//根据贪心思想，能往前走就往前走6         v=fa[k][v];
      
     

　　2.基于Tarjan的LCA

　　　　算法流程请看参考资料[2]，下面谈谈我对此算法得理解；

　　　　对于某一结点 i ，如果询问中存在点对(u,v)使得 u∈i 的某一颗子树，v∈ i 的另一颗子树，那么Lca(u,v) = i；

　　　　根据算法流程，由节点 i 向下搜索其中一颗子树时，假设为u所在的子树，但此前并没有搜索到v所在的子树，

　　　　当来到u节点时，此时vis[ v ] =false，并将fa[u]=其父亲节点,vis[u]=true；

　　　　在往上回溯过程中，再一次来到 i 节点，根据并查集可得 fa[u]=i ；

　　　　继续执行搜索过程，来到另一颗子树，假设为v所在的子树，当来到v节点时，vis[ u ]=true，说明之前搜索过u节点，那么

　　　　Lca(u,v) = fa[u] = i；

　　3.基于ST()的LCA

　　　　算法介绍请看参考资料[3]，讲的超详细；

　　　　我的算法模板：

1 /** 2     LCA:DFS+ST() 3 */ 4 #include
      
        5 #include
       
         6 #include
        
          7 #include
         
           8 using namespace std; 9 #define mem(a,b) memset(a,b,sizeof(a))10 #define ll long long11 const int maxn=1e5+50;12 13 int n,m;14 int num;15 int head[maxn];16 ll dis[maxn];17 struct Edge18 {19     int to;20     ll w;21     int next;22 }G[maxn<<1];23 void addEdge(int u,int v,ll w)24 {25     G[num]=Edge{v,w,head[u]};26     head[u]=num++;27 }28 struct LCA29 {30     /**31         个人习惯数组下标从1开始32         此模板的下标从1开始33     */34     int vs[maxn<<1];///欧拉序列35     int dep[maxn<<1];///欧拉序列对应的深度序列36     int pos[maxn];///pos[i]:节点i在欧拉序列中第一次出现的位置37     int cnt;38     int logTwo[maxn<<1];///logTwo[i]=log2(i)39     int dp[maxn<<1][20];40     void DFS(int u,int f,int depth,ll dist)41     {42         vs[++cnt]=u;43         dep[cnt]=depth;44         pos[u]=cnt;45         dis[u]=dist;46         for(int i=head[u];~i;i=G[i].next)47         {48             int v=G[i].to;49             int w=G[i].w;50             if(v == f)51                 continue;52             DFS(v,u,depth+1,dist+w);53             vs[++cnt]=u;54             dep[cnt]=depth;55         }56     }57     void ST()58     {59         ///预处理出dp[i][j],logTwo[i]60         logTwo[0]=-1;61         for(int i=1;i <= cnt;++i)62         {63             dp[i][0]=i;64             ///111(2)->1000(2):(111)&(1000)=0,logTwo[1000]=logTwo[111]+165             logTwo[i]=((i&(i-1)) == 0) ? logTwo[i-1]+1:logTwo[i-1];66         }67         for(int k=1;k <= logTwo[cnt];++k)68             for(int i=1;i+(1<
          
           <= cnt;++i)69                 if(dep[dp[i][k-1]] > dep[dp[i+(1<<(k-1))][k-1]])70                     dp[i][k]=dp[i+(1<<(k-1))][k-1];71                 else72                     dp[i][k]=dp[i][k-1];73     }74     void lcaInit(int root)75     {76         cnt=0;77         DFS(root,root,0,0);78         ST();79     }80     int lca(int u,int v)///返回u,v的公共祖先81     {82         u=pos[u];83         v=pos[v];84         if(u > v)85             swap(u,v);86         int k=logTwo[v-u+1];87         if(dep[dp[u][k]] > dep[dp[v-(1<