LCA+倍增淺析

介紹：

LCA即為求在一棵樹上的兩點a,b的最近公共祖先。

最近公共祖先是什麼？

顧名思義，如果有一個點x是a和b的祖先，且x到a和b的距離最短，那麼x就是a,b的最近公共祖先。

應用：

LCA多用于求樹上兩點間最短路徑（即為不重複路徑）上的權值和、最值問題。

為什麼？

因為最短路徑（不重複路徑）說明了這條路徑要經過它們的最近公共祖先，也可以了解為從它們的最近公共祖先出發分别走到它們自己。

LCA實作：

考慮搜尋記錄下a,b兩點的深度。

如果a的深度>b的深度，則不斷把a上升到它父親，直到a的深度=b的深度。

反之，如果b的深度>a的深度，則不斷把b上升到它父親，直到b的深度=a的深度。

好了，我們現在已經使a和b處在同一深度。

我們現在要做的就是，把a和b每次各自上升到它們的父親，直到它們相同。

那麼a,b相同之後最近公共祖先就是a（或者說是b）了。

但是這樣一個個往上升會很慢，怎麼辦呢？

我們可以考慮使用倍增。

倍增的思想及自創的僞倍增：

既然一個個往上升會很慢，那麼我們如果能幾個幾個甚至幾百幾千地往上升，就會快很多了。

——這便是倍增的思想。

但是，如果我們想一次往上升x個位置，就需要知道每個點的第x個祖先是多少。

怎麼去記錄呢？

在還沒系統地學倍增之前，我是這樣想的：

比如說樹的深度是100000，

我們先記錄每個點的第10000個祖先是什麼，第1000個祖先是什麼，第100個祖先是什麼，第10個祖先是什麼，以及第1個祖先（它的父親）是什麼。

至于如何去記錄，可以在用dfs建樹的過程中開個數組，記錄從根節點到目前節點所經過的點（也就是目前點的所有祖先），然後每次把目前點的第10000個祖先、第1000個祖先、第100個祖先、第10個祖先、第1個祖先記錄下來。

然後我們往上升的時候就可以先一萬個一萬個地升，當它離它的目标深度差小于一萬時再一千個一千個地升，以此類推，最後當它離它的目标深度小于10時一個一個地升，用幾個while循環去實作。

這樣做LCA的時候，我們就可以在n*log10（n）内求出它的最近公共祖先。

至于這樣做LCA的具體操作實作，因為與下文的真正倍增大體相同，在這裡就不講了，留到下文再講。

但是，通常LCA的應用不會讓你隻去求兩點的最近公共祖先，還可能會讓你求樹上兩點間最短路徑的權值和、最小最大權值。

而這種倍增隻能通過記錄從根節點到每個節點的字首和求出路徑中的權值和，卻無法求出最小最大權值。

是以，我管這種不能記錄最值的方法叫僞倍增。

那麼，如何去解決求樹上兩點間最短路徑的最小最大權值呢？

就要用到真正的倍增了。

真正的倍增：

真正的倍增的思想類似于RMQ。

我們設f[i][j]表示點i的第2^j個祖先。

因為2^（j-1）*2=2^j，

如圖，是以對于點i來說，它的第2^j個祖先就等于它的第2^（j-1）個祖先的第2^（j-1）個祖先。

是以我們就可以得到轉移方程f[i][j]=f[f[i][j-1]][j-1]。

因為轉移方程中f[i][j-1]>i，是以按j來分層，轉移的時候先從小到大枚舉j，再從小到大枚舉i。

如果我們要求出路徑中的最小值（最大值同理），

那麼也一樣可以類似地設g[i][j]表示從第i個點到第i個點的第2^j個祖先這段路徑的最小值。

轉移方程同理：g[i][j]=min(g[i][j-1],g[f[i][j-1]][j-1]);

就是說把它分成兩半，再從這兩半的答案中取個最小值。

如果說要求出路徑中的權值和也同理，

g[i][j]=g[i][j-1]+g[f[i][j-1]][j-1];

好了，到現在為止我們已經預處理得到了f數組和g數組，

那麼，如何通過倍增做LCA呢？

LCA+倍增的實作：

前面我們已經知道了普通LCA的做法：

1、先調深度，把深度調至相同；

2、兩點同時上升，直到它們相同。

那麼，先看調深度，我們如何用倍增實作調深度呢？

我們假設兩點x,y中較深的那個點是x，它們的深度差為t。

那就相當于我們要把點x上升到它的第t個祖先。

我們設一個k，使得2^k<=t，每次x=f[x][k];  t-=2^k； k--; 

可以用while循環去實作。

打一下核心代碼：

k=30;
while (t>0)
{
    if ((1<<k)<=t) 
    {
         t-=1<<k;
         x=f[x][k];
    }
    k--;
}
           

如果有求和求最值操作的，在裡面把那個g數組加上去就好了。

好了，現在深度已經相同了，我們轉入操作2：兩點同時上升，直到它們相同。

我們還是設一個k，使得深度deep>(1<<k)。

如果f[x][k]=f[y][k]就表示目前如果往上跳的話可能會跳過它們的最近公共祖先，是以就不跳，k--；

否則如果f[x][k]！=f[y][k]就跳，因為這樣肯定不會超過它的最近公共祖先。

還是打一個僞代碼:

k=30;
while (k>=0)
{
     if (deep>(1<<k) && f[x][k]!=f[y][k])
     {
          deep-=(1<<k);
          x=f[x][k];
          y=f[y][k];     
     }
     k--;
}
           

這樣做完以後，x,y都成了它們最近公共祖先的直系兒子，是以最近公共祖先就是現在x的父親（或者說是y的父親）。

是以呢，LCA和倍增就講完了，

如果講解内容或僞代碼有任何問題，歡迎留言提醒，

如果覺得寫得好，歡迎點贊和轉發，

謝謝！