LCA（Lowest Common Ancestor）

定義

在樹上取兩點?x,yx,y，他們的 LCA 為距離他們最近的公共祖先。

本章主要講的是倍增求 LCA。

暴力求取

1. 從?xx?開始向上移動到根結(jié)點，并標記沿途結(jié)點。
2. 從?yy?開始向上移動到根結(jié)點，第一個被標記的就是?xx?和?yy?的 LCA。

倍增求 LCA

從任意點對?(x,y)(x,y)?移到?xx?和?yy?的 LCA 的距離可拆分為?22?的冪的和。

若預(yù)處理任意點?xx?移動?22?的冪步所到達的結(jié)點編號，則不超過?\log_2{n}log2?n?次即可找到 LCA。

具體實現(xiàn)

first：預(yù)處理倍增 DP

定義狀態(tài)?dp_{i,j}dpi,j??表示點?ii?向上移動?2^j2j?步到達的結(jié)點編號。

狀態(tài)轉(zhuǎn)移方程：枚舉?jj?從?11?到?\log_2 nlog2?n，dp_{i,j}=dp_{dp_{i,j-1},j-1}dpi,j?=dpdpi,j?1?,j?1?。

初始狀態(tài)：dp_{i,0}=fa_idpi,0?=fai?。

代碼片段

void pre_lca(int cur, int fa)
{dep[cur]=dep[fa]+1;dp[cur][0]=fa;for(int i=1;(1<<i)<=dep[cur];i++){dp[cur][i]=dp[dp[cur][i-1]][i-1];}for(int nxt:nbr[cur]){if(nxt!=fa)pre_lca(nxt,cur);}
}

second：處理單次詢問

第一步：約定深度較大的點，若?dep_x>dep_ydepx?>depy?，交換?xx?和?yy。

第二步：將深度較大的結(jié)點?yy?倍增向上跳至深度等于?xx。

第三步：判斷?xx?是否等于?yy。若已經(jīng)相等則?xx?為 LCA，停止尋找。

第四步：xx?和?yy?一起倍增向上跳，只要?xx?和?yy?不重合。

第五步：xx?向上一步即為 LCA。

代碼片段

int lca(int x, int y)
{if(dep[y]<dep[x])swap(x,y);for(int i=20;i>-1;i--){if(dep[dp[y][i]]>=dep[x]){y=dp[y][i];}}if(x==y)return x;for(int i=20;i>-1;i--){if(dp[x][i]!=dp[y][i]){x=dp[x][i],y=dp[y][i];}}return dp[x][0];
}

時間復(fù)雜度

預(yù)處理是?O(n \log_2 n)O(nlog2?n)?的，中間單次求取僅為?O(n)O(n)

模板代碼

#include<bits/stdc++.h>
#define int long long
using namespace std;
int dp[500005][21],dep[500005], n, m, s;
vector<int> nbr[500005];
void pre_lca(int cur, int fa)
{dep[cur]=dep[fa]+1;dp[cur][0]=fa;for(int i=1;(1<<i)<=dep[cur];i++){dp[cur][i]=dp[dp[cur][i-1]][i-1];}for(int nxt:nbr[cur]){if(nxt!=fa)pre_lca(nxt,cur);}
}
int lca(int x, int y)
{if(dep[y]<dep[x])swap(x,y);for(int i=20;i>-1;i--){if(dep[dp[y][i]]>=dep[x]){y=dp[y][i];}}if(x==y)return x;for(int i=20;i>-1;i--){if(dp[x][i]!=dp[y][i]){x=dp[x][i],y=dp[y][i];}}return dp[x][0];
}
signed main()
{ios::sync_with_stdio(0),cin.tie(0);cin>>n>>m>>s;for(int i=1;i<n;i++){int x, y;cin>>x>>y;nbr[x].push_back(y);nbr[y].push_back(x);}pre_lca(s,0);for(int i=1;i<=m;i++){int x, y;cin>>x>>y;cout<<lca(x,y)<<"\n";}
}

LCA 應(yīng)用

1. 求樹上兩點之間距離。
2. 樹上差分。

LCA 求樹上兩點之間距離

維護?dis_xdisx??表示根結(jié)點到?xx?的距離。

xx?到?yy?的簡單路徑的長度為?dis_x+dis_y-2\times dis_{\texttt{lca}(x,y)}disx?+disy??2×dislca(x,y)?。

LCA 例題

first：P5836

方法 1

點權(quán)可以轉(zhuǎn)為?00?或?11，維護?dis_idisi??表示由根結(jié)點到?ii?的距離。

維護深度?dep_idepi?，對于每次詢問，若?(dis[a]+dis[b]-2*dis[lcad]+w[lcad]==dep[a]+dep[b]-2*dep[lcad]+1)&&c!='H'?或?dis[a]+dis[b]-2*dis[lcad]+w[lcad]==0&&c=='H'?則輸出?00，否則輸出?11。

方法 2

若一條邊的兩個端點的?ww?相同，則?unionn?這兩個端點。

若一條路徑上點權(quán)相同，則兩個端點一定在同一集合。若該集合的權(quán)值不等于詢問，輸出?00，否則輸出?11。

while(m--)
{int x, y;char c;cin>>x>>y>>c;if(c=='H'){cout<<!(find(x)==find(y)&&w[x]==0);}else{cout<<!(find(x)==find(y)&&w[x]==1);}
}

方法 3

維護?dp_{i,j}dpi,j??表示?ii?向上動?2^j2j?步到達的結(jié)點編號，維護?yes_{i,j,0/1}yesi,j,0/1??表示?ii?向上跳?2^j2j?步是否有?ww?為?0/10/1?的點。

yes[cur][i][0]=yes[cur][i-1][0]|yes[dp[cur][i-1]][i-1][0],yes[cur][i][1]=yes[cur][i-1][1]|yes[dp[cur][i-1]][i-1][1];。

初始狀態(tài)：dp_{i,0}=fa_idpi,0?=fai?，yes_{i,0,w_{fa}}=1yesi,0,wfa??=1。

second：CF519E

若?AA?到?BB?的距離為奇數(shù)，則答案直接為?00。

否則分情況討論：

1. 中間位置的點?x=lcax=lca

   xx?兒子結(jié)點中包含?AA?和?BB?的子樹剔除，其余為答案。

2. 中間位置的點?xx?不是?lcalca

   約定深度較大的點為?BB，找到?BB?向上距離?xx?一步的點?pp，則答案為?size_x-size_psizex??sizep?。

注意特殊情況：A==BA==B?時，答案為?nn。

從?lcalca?到?xx?的距離為?\frac{dep_B-dep_A}{2}2depB??depA??。

void work(int x,int y)
{if(x==y){cout<<n<<"\n";return ;}if(dep[x]==dep[y]){for(int i=14;i>=0;i--){if(dp[x][i]!=dp[y][i]){x=dp[x][i],y=dp[y][i];}}cout<<size[1]-size[x]-size[y]<<"\n";return  ;}if(dep[x]<dep[y]) swap(x,y);if((dep[x]-dep[y])%2==1){cout<<"0\n";return ;}int x2=x,len=(dep[x]-dep[y])/2;for(int i=14;i>=0;i--){if(dep[dp[x][i]]>=dep[y]){x=dp[x][i];}}if(x==y){len+=dep[x];for(int i=14;i>=0;i--){if(dep[dp[x2][i]]>len){x2=dp[x2][i];}}cout<<size[dp[x2][0]]-size[x2]<<"\n";return ;}for(int i=14;i>=0;i--){if(dp[x][i]!=dp[y][i]){x=dp[x][i],y=dp[y][i];}}len+=dep[x]-1;for(int i=14;i>=0;i--){if(dep[dp[x2][i]]>len){x2=dp[x2][i];}}cout<<size[dp[x2][0]]-size[x2]<<"\n";
}

Third：P8972 一切都已過去

見?題解：P8972 『GROI-R1』 一切都已過去 - 洛谷專欄

方便閱讀搬過來。

從數(shù)據(jù)范圍很容易發(fā)現(xiàn)，如果我們把邊權(quán)累乘再判整數(shù)，炸掉是必然的，這時候，我們來發(fā)現(xiàn)一個性質(zhì)：只有小數(shù)部分有?22?和?55?相乘的時候，才可能變成整數(shù)。當然，這并不是絕對的，例如?2.02 \times 52.02×5?就不是整數(shù)。從上面舉的例子很容易發(fā)現(xiàn)一個性質(zhì)：兩個實數(shù)的乘積是否為整數(shù)與小數(shù)點數(shù)位也有關(guān)系。一對?22?和?55?可以抵消掉一個小數(shù)點數(shù)位（22?和?55?可以在任意且不同數(shù)位上，并且?22?和?55?的倍數(shù)也有用）。這時，我們可以將邊權(quán)通過不斷?\times 10×10?變成整數(shù)，并分解質(zhì)因數(shù)分別求因數(shù)中?22?和?55?的個數(shù)（點權(quán)也要處理）。22?和?55?的個數(shù)求出來了，小數(shù)點數(shù)位也很好處理。最終的小數(shù)點位數(shù)應(yīng)該是所有路徑上的邊權(quán)小數(shù)點位數(shù)之和，所以我們在將邊權(quán)化整數(shù)時再維護一個變量統(tǒng)計小數(shù)點位數(shù)并記錄到鄰接矩陣里。若路徑?xx?到?yy?的總邊權(quán)乘上?xx?的點權(quán)得到的結(jié)果中?22?的個數(shù)和?55?的個數(shù)大于或等于總小數(shù)點位數(shù)，則其為整數(shù)。分別維護即可。

注意：若邊權(quán)或點權(quán)為?00?則對應(yīng)維護的當前點權(quán)或點權(quán)的?22?和?55?賦予極大值。

Latex有雙倍問題，完整版請在安全訪問中心 - 洛谷查看