這篇筆記說明 Tarjan's offline Lowest Common Ancestor (LCA) algorithm。

對於一個rooted tree，有許多查詢，對每一個查詢(u,v)，要找出u與v的LCA，offline的意思是想要查詢的對象事先已經知道。Tarjan用一個簡單的DFS就完成此事。
在Tree的問題中，LCA是一個重要的問題，最常見到的運用就是查詢兩點之間的距離，例如我們有很多對(u,v)要查詢兩點在樹上的距離。

若對所有點v皆以計算出$v$點的深度 $depth[v]$，也就是$v$點到root的距離，那麼
$d(u,v) = depth[u]+depth[v]-2\times depth[lca(u,v)]$。


以這個例子來看，$depth[1]=3$、$depth[4]=7$，$lca(1,4)=3$、$depth[3]=1$。
$d(1,4) = 3+7-2\times 1 = 8$。

所以，要進行距離的查詢，我們只需要計算所有點的深度，以及所要查詢點對的LCA。
計算深度可以很簡單的用一個DFS來完成，以下來說明如何用一個DFS完成LCA的計算。Tarjan's algorithm的原理很簡單，首先，我們要知道，我DFS的過程中，我們其實有意或無意的維護了一個迴圈不變性：當走訪到點$v$時，我們其實維護了root到$v$的那條path。有時候我們會把這路徑建出來，雖然有時並不明顯的建立，但這條路徑就是那些遞迴走訪到而尚未走訪完成的點。為了方便讀者理解，以下我們先用一個程式示範基本的以DFS計算depth以及把這條路徑建出來。

edges = [[0,3,1],[0,5,2],[3,1,2],[3,6,4],[6,2,3],[4,6,2]]
n = 7
queries = [[0,6],[6,4],[1,5],[1,4]]
# build adj
adj = [[] for i in range(n)]
for u,v,w in edges:
    adj[u].append((v,w))
    adj[v].append((u,w))
#
root = 0
depth = [-1]*n # -1 for unvisited
depth[root] = 0
path = []
def dfs(v):
    path.append(v);
    print(f"path from {root} to {v} is {path}")
    for u,w in adj[v]: # (edge (v,u) with weight w
        if depth[u] >= 0: continue # parent of v
        depth[u] = depth[v]+w
        dfs(u)
    #
    path.pop()
#
dfs(root)
print("depth:",depth)

執行結果

path from 0 to 0 is [0]
path from 0 to 3 is [0, 3]
path from 0 to 1 is [0, 3, 1]
path from 0 to 6 is [0, 3, 6]
path from 0 to 2 is [0, 3, 6, 2]
path from 0 to 4 is [0, 3, 6, 4]
path from 0 to 5 is [0, 5]
depth: [0, 3, 8, 1, 7, 2, 5]

LCA演算法的原理是這樣的，當走訪到$v$時，若$(u,v)$是要查詢的點對，且**u點已經走訪過了**，那麼lca(u,v)就是「u在該path上的最低祖先」，以上面的例子來說，到4時，path=[0,3,6,4]，此時已走訪過的點是(0,3,1,6,2,4)，對點1來說，$lca(1,4)=3$。

要查詢u點在path上的最低祖先要怎麼做呢？直接的做法就是往上一步一步爬，爬到碰到該path時就是答案。問題是這樣爬太慢，解決之道是運用disjoint set (union and find)資料結構中的**路徑壓縮**。
使用一個陣列anc[v]，初始時，anc[v]=v，當v被走訪**完畢**時，anc[v]會紀錄v的parent，所以沿著anc往上走直到anc[x]==x的點時，x即是v點在path上的最低祖先。
對於一個已經走訪過的點來說，他將來要被查詢的祖先只會往上，而不會往下，所以當他被查詢之後，我們可以將anc[v]直接改成x，也就是把v到x的那條路徑壓縮掉，好處是將來查詢v以及它的後代時，路徑就會變短(這部分如果不了解，可以再去看disjoint set的資料結構)。

程式寫起來非常簡單，以下是範例程式。

edges = [[0,3,1],[0,5,2],[3,1,2],[3,6,4],[6,2,3],[4,6,2]]
n = 7
queries = [[0,6],[6,4],[1,5],[1,4]]
# build adj
adj = [[] for i in range(n)]
for u,v,w in edges:
    adj[u].append((v,w))
    adj[v].append((u,w))
#
root = 0
depth = [-1]*n # -1 for unvisited
depth[root] = 0
#path = []
# prepare for lca query
other = [[] for i in range(n)]
for u,v in queries:
    other[u].append(v)
    other[v].append(u)
lca = {}    
anc = list(range(n)) # anc[v]==v is on path
def find(v):
    if anc[v] == v: return v
    anc[v] = find(anc[v])
    return anc[v]

def dfs(v):
    #path.append(v);
    #print(f"path from {root} to {v} is {path}")
    for u,w in adj[v]: # (edge (v,u) with weight w
        if depth[u] >= 0: continue # parent of v
        depth[u] = depth[v]+w
        dfs(u)
        anc[u] = v # union
    #
    for u in other[v]:
        if depth[u] < 0: continue # unvisited
        x = find(u)
        lca[u,v] = x
    # path.pop()
#
dfs(root)
print("depth:",depth)
print("LCA:",lca)

留意到第21 ~ 24行的find(v)，這個就是路徑壓縮，利用遞迴的方式找到祖先，並且把沿路上的點都直接拉上去。DFS城市中只有第33行是在u點走訪完畢後設定anc[u]，第35 ~ 38行是查詢v的對象u，其中depth[u]必須非負才是走過的點。
執行結果如下：

depth: [0, 3, 8, 1, 7, 2, 5]
LCA: {(6, 4): 6, (1, 4): 3, (0, 6): 0, (4, 6): 6, (1, 5): 0, (6, 0): 0}

LeetCode中LCA的題目例如 3585, 3559, 3553。