Today，we will talk about how to find The Least Common Ancestor.

Now ,let us get into the business（正题）.

为了大家可以更好地理解......

I will use chinese. 好吧，我装不下去了.

 

写在前面：

会有人问，不写最简单的暴力，一开始就写倍增实现，会不会有点太唐突。我想说，其实二者思路几乎一致，后者只是前者稍微修改一下而已。明白了倍增，暴力几乎对着打。

 

开始对LCA的讲解：

　　LCA是啥？吃？，LCA表示在树上两点之间的最近公共祖先。

　　以下图为例，手工画作可能会比较粗糙，凑合着看吧。

2 和 3的 LCA 是多少呢 ? 显然他们只有 1 一个祖先，所以1 没毛病。

那么 5 和 8 的 LCA是是多少呢？ 8->4->2 , 5->2, 所以他的们的 LCA是 4.

那么如何实现LCA呢？

首先定义几个数组：

　　deep[ i ]数组表示第 i 个节点所在的深度层数。

　　up[ i ][ j ] , 注意是个二维数组，表示第 i 个节点向上 2^j 层所到达的节点，，例如上图p[13][1]=4。

　　dis[ i ][ j ]，也是二维哦，表示从第 i 个点向上 2^j 层上的那个点的权值(也就是距离)，若权值都唯一，可忽略。

当然你还需要连边建树：

　　这就不多bb了。

int head[maxn],tot;void add(int x,int y){    edge[++tot].nxt=head[x],edge[tot].to=y;head[x]=tot;　　// 注意一下双向边}

开始分析：

　　deep[ ]数组：

　　　　deep[x]=deep[ fa[x] ]+1,fa[x]表示x的父节点，这点很显然，没啥好说的。 

　　up[ ][ ]数组 ：

　　　　这个数组比较有意思，确切的说是 关于2的乘方 比较好玩了。

　　　　up[ x ][ i ] = up[ up[ x ][ i-1 ] ][i-1] (颜色区分下),

　　　　你可以理解为 2ⁱ = 2^i-1 + 2^i-1 。

　　　　有问题？那么我们可以一步一步探讨一下。

　　　　先看标记部分先跳到x向上 2^i-1 个点，记为u点，那么再从u点向上 2^j-1 层，则相对于x点来说不就可以看作 向上2 * 2^i-1 =2ⁱ 层么。

　　　　还不理解的话，可以从图上手动演示下。

　　dis[ ][ ]数组：

　　　　dis[ i ][ j ] = dis[ i ][ j-1 ] + dis[ up[ i ][ j-1 ] ][ j-1 ].

　　　　若已经明白以上 up 数组 则明白这个性质了，在这不不做过多解释(不明白？按照上图手演)。

开始dfs预处理部分：

　　通过对以上数组的解释这部分几乎已经讲解完了。

　　看代码，可能会更好的帮你理解：

void dfs(int u,int fa)        // u表示当前节点，fa表示其父节点。 {    deep[u]=deep[fa]+1; p[u][0]=fa;        //这行没啥问题。     for(int i=1;(1<
     
      <=deep[u];i++)p[u][i]=p[p[u][i-1]][i-1];    //深度跳跃，上边有解释。     for(int i=head[u];i;i=edge[i].nxt)        if(edge[i].to!=fa)dfs(edge[i].to,u);    // if判断是否是节点的爸爸，因为他们之间有边啊 }
     

 

那么开始实现LCA了吧：

　　1.首先我们需要判断一下谁深谁浅，记所求LCA的两点位a，b。

　　这简单，

if(deep[a]>deep[b])swap(a,b);

　　确保a比b浅，也就是在树上，a点相比较于b点较高。

　　2.将两点转化为在同一深度。

　　那么a点比较高，那么就从b点开始往上跳吧。

　　先代码，后解释。

for(int i=20;i>=0;i--)    if(deep[a]<=deep[b]-(1<

　　注意这时候向上跳的i我们需要从大数开始枚举，20的话足够大了，想..2²⁰多少层了。

　　我们不允许b点跳的比a高，若b点向上跳，跳不超，那么就让b向上跳。

　　这里还是 2的乘方 的性质，循环过后，他两个一定在同一层(why? 小于2ⁱ的数绝对可以用x(x<i),相加得到 )。

　　3.特判一下(避免浪费时间)

　　if(a==b)return a;

　　4.一起往上跳

　　for(int i=20;i>=0;i--)    {        if(p[a][i]==p[b][i])continue;        else a=p[a][i],b=p[b][i];    }

　　跳完以后他们就在同一深度，并且a和b任意一个节点的父节点，为a和b的公共祖先，都是父节点了，当然是最近的咯。

这一部分代码：

int lca(int a,int b){    if(deep[a]>deep[b])swap(a,b);    for(int i=20;i>=0;i--)    if(deep[a]<=deep[b]-(1<
     
      =0;i--)    {        if(p[a][i]==p[b][i])continue;        else a=p[a][i],b=p[b][i];    }    return p[a][0];}
     

　　

luogu P3379 

代码：

#include 
     
      #include 
      
       #include 
       
        #define maxn int(5e5+2)using namespace std;struct ahah{    int nxt,to;}edge[maxn];int n,m,s;int head[maxn],tot;void add(int x,int y){    edge[++tot].nxt=head[x],edge[tot].to=y;head[x]=tot;}int deep[maxn],p[maxn][22];void dfs(int u,int fa)        // u表示当前节点，fa表示其父节点。 {    deep[u]=deep[fa]+1; p[u][0]=fa;        //这行没啥问题。     for(int i=1;(1<
        
         <=deep[u];i++)p[u][i]=p[p[u][i-1]][i-1];    //深度跳跃，上边有解释。     for(int i=head[u];i;i=edge[i].nxt)        if(edge[i].to!=fa)dfs(edge[i].to,u);    // if判断是否是节点的爸爸，因为他们之间有边啊 }int lca(int a,int b){    if(deep[a]>deep[b])swap(a,b);    for(int i=20;i>=0;i--)    if(deep[a]<=deep[b]-(1<
         
          =0;i--)    {        if(p[a][i]==p[b][i])continue;        else a=p[a][i],b=p[b][i];    }    return p[a][0];}int main(){    int a,b;    scanf("%d%d%d",&n,&m,&s);    for(int i=1;i
         
        
       
      
     

　　

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define max 40001#define maxl 25using namespace std;typedef struct{    int from,to,w;}edge;//这个结构体用来存储边 vector
           
            edges;vector
            
              G[max];//保存边的数组int grand[max][maxl],gw[max][maxl];//x向上跳2^i次方的节点，x到他上面祖先2^i次方的距离int depth[max];//深度int n,m,N;void addedge(int x,int y,int w)//把边保存起来的函数{ edge a={x,y,w},b={y,x,w}; edges.push_back(a); edges.push_back(b); G[x].push_back(edges.size()-2); G[y].push_back(edges.size()-1);}void dfs(int x)//dfs建图{ for(int i=1;i<=N;i++)//第一个几点就全部都是0咯，第二个节点就有变化了，不理解的话建议复制代码输出下这些数组 { grand[x][i]=grand[grand[x][i-1]][i-1]; gw[x][i]=gw[x][i-1]+gw[grand[x][i-1]][i-1]; // if(grand[x][i]==0) break; } for(int i=0;i
             
               depth[b]) swap(a, b);//保证a在b上面，便于计算 int ans = 0; for(int i = N; i >= 0; i--) //类似于二进制拆分，从大到小尝试 if(depth[a] < depth[b] && depth[grand[b][i]] >= depth[a])//a在b下面且b向上跳后不会到a上面 ans +=gw[b][i], b=grand[b][i];//先把深度较大的b往上跳 for(int j=N;j>=0;j--)//在同一高度了,他们一起向上跳,跳他们不相同节点，当全都跳完之后grand【a】【0】就是lca,上面有解释哈。 { if(grand[a][j]!=grand[b][j]) { ans+=gw[a][j]; ans+=gw[b][j]; a=grand[a][j]; b=grand[b][j]; } } if(a!=b)//a等于b的情况就是上面土色字体的那种情况 { ans+=gw[a][0],ans+=gw[b][0]; } return ans;}int main(){ int t ; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); for(int i=1;i