<style type="text/css"> .slides { text-align: left !important; } </style> # LCA 最低共同祖先 #### Author:H1de_on_bruH ---- ## 概要 基本知識 作法們 例題們 --- ## 基本知識 >樹:一個有$N$個節點$N-1$條邊且沒有環的圖 >根:那個最上面的那個節點 可以做任意一個節點的祖先 >祖先:若節點u往上走可以到達節點v 則我們稱節點v為節點u的祖先 ---- 設$x$為$u$跟$v$的LCA 那$x$必在$u$到$v$的路徑上且是路徑上所有點中深度最小的 --- ## 作法們 ---- ### 倍增法 ---- 想像一下 我們如果用爆搜的方法要怎麼找? ---- 先把兩個點的高度升到一樣 然後兩個都用同樣的速度往上走 直到碰到同一個點 那這個點就會是這兩個點的LCA ---- 一次查詢的複雜度$O(N)$ 有沒有方法讓他更快? ---- #### 倍增的性質 我們先做好一個陣列 我們叫他$f_{ij}$ 這個數代表$i$往上走$2^j$個點會到哪個點 這可以在$O(N\log N)$的時間完成 ---- 我們在往上爬x格的時候 可以把x換成2的冪次和 例如: $5=2^2+2^0$ $8=2^3$ ---- 那這樣做$\log N$次就可以把高度上升$N$ 複雜度$O(\log N)$ ---- ##### 實作 $f_{ij}$的預處理 ```cpp= void dfs(int now,int par,int counter){ f[now][0]=par; h[now]=counter;//維護深度 for(int i:path[now]) if(i!=par)dfs(i,now,counter+1); } ``` 先遍歷一次樹 把所有往上$2^0$的資料先寫好 ---- ```cpp= for(int j=1;j<=20;j++) for(int i=1;i<=n;i++) f[i][j]=f[f[i][j-1]][j-1]; ``` $i$上升$2^j$格就會等於$i$上升了$2^{j-1}$後又再上升$2^{j-1}$格 這裡注意$j$要在最外圈且由小到大做 ---- 找LCA ```cpp= int LCA(int a,int b){ //我們先預設a的深度必須低於b 這樣比較方便實作 if(h[a]>h[b])return LCA(b,a); for(int i=h[b]-h[a],k=0;i;i>>=1,k++) if(i&1)b=f[b][k];//先讓他們上升到同樣的高度 //如果a=b 表示他們到同樣高度後節點會是一樣 那a就是LCA if(a==b)return a; for(int i=20;i>=0;i--) if(f[a][i]!=f[b][i]){ a=f[a][i]; b=f[b][i]; } return f[a][0]; } ``` 核心就是先把$a b$升到依樣高度 然後再往上二分搜 也就是看升高$2^i$格時 會不會碰在一起 ---- 就是讓他們兩個越來越接近 但不能靠在一起 那最後找到的點就會是LCA的子節點 這時候回傳這個點的父親就會是正確的答案了 ---- ### 樹壓平+RMQ(毒瘤) ---- 何謂樹壓平? >把樹壓成陣列表示 ----  ---- 對a跟b中間的所有點找最淺的那個點 那找到的點就會是LCA 實作跟細節我就不帶了這我也沒有甚麼研究 通常用倍增法就可以應付多數的題目了 除非題目的查詢次數到$10^7$量級 ~~爛題目 不要寫~~ --- ## 例題們 ---- [CSES#1688](https://cses.fi/problemset/task/1688) 裸題 直接抄模板就會過 ---- [CSES#1135](https://cses.fi/problemset/task/1135) 也是很裸 找到LCA後輸出$h_a+h_b-2\times h_{LCA}$就會對了 ---- [TIOJ#1163](https://tioj.ck.tp.edu.tw/problems/1163) 先備知識:最小生成樹(Minimum Spaning Tree) 先生出一棵MST後 對詢問的點找LCA 那你同時也維護一個$mx_{ij}$ 表示在$i$上升$2^j$格的路上邊的最大值 這個陣列也可以在$O(N\log N)$的複雜度處理完 這樣找到LCA後就可以分兩邊做 用$O(\log N)$往上移 紀錄最大值後就會有答案了 [點我看AC code](https://pastebin.com/FAKbwkSf) --- ### 以上 我覺得LCA的題目都還蠻有趣的 ~~只是我倍增法一直寫爆我也不知道為甚麼X_X~~ ---- >W<