§06 图结构

LCA 最近公共祖先

倍增上跳:深的先追平、两点同步试跳——树上差分与距离计算的基础。

LCA 最近公共祖先

第 01 / 10 步

树上倍增 LCA: 已预处理每个节点的深度与 2^k 级祖先。查询 LCA(G, F)。比较 0 · 交换 0

伪代码


				
					
					1
					procedure LCA(u, v)
				
			
				
					
					2
					  预处理: depth[u] 与 up[u][k] = 2^k 级祖先
				
			
				
					
					3
					  if depth[u] < depth[v]: 交换 u, v        // 让 u 更深
				
			
				
					
					4
					  diff = depth[u] - depth[v]
				
			
				
					
					5
					  for k = 0..LOG-1: if diff 第 k 位为 1: u = up[u][k]
				
			
				
					
					6
					  if u == v: return u
				
			
				
					
					7
					  for k = LOG-1..0:
				
			
				
					
					8
					    if up[u][k] != up[v][k]: u=up[u][k]; v=up[v][k]
				
			
				
					
					9
					  return up[u][0]                       // 父节点即 LCA

01 / 10

速度