• LCA问题，就是最近公共祖先的问题

习题

1483.树节点的第K个祖先

1483.树节点的第K个祖先

• 普通的做法，当然是一个个往上面搜索，但是这样的话时间复杂度是o(k),那么能不能每次求解的是爷爷节点，这样就是按照二进制的步子进行寻找

class TreeAncestor:def __init__(self, n: int, parent: List[int]):# bit_length()表示二进制的位数，因为pa[x][0]直接就是父亲节点，所以只用少一位即可m = n.bit_length() - 1# 初始化pa = [[p] + [-1]*m for p in parent]# 注意这个遍历，先枚举这个i再枚举这个x,先算出全部节点的所有爷爷节点，再算出所有爷爷的爷爷节点for i in  range(m):for x in range(n):p = pa[x][i]if p != -1:pa[x][i+1] = pa[p][i]self.pa = padef getKthAncestor(self, node: int, k: int) -> int:for i in range(k.bit_length()):# 这个k>>i的判断就十分巧妙# 并且这个node 是全局的，i从0开始判断if (k >> i) & 1:node = self.pa[node][i]if node < 0 :breakreturn node

拓展：LCA

• 初始化

# 

class TreeAncestor:def __init__(self, edges: List[List[int]]):n = len(edges) + 1m = n.bit_length()g = [[] for _ in range(n)]for x, y in edges:  # 节点编号从 0 开始g[x].append(y)g[y].append(x)depth = [0] * npa = [[-1] * m for _ in range(n)]def dfs(x: int, fa: int) -> None:pa[x][0] = fafor y in g[x]:if y != fa:depth[y] = depth[x] + 1dfs(y, x)dfs(0, -1)for i in range(m - 1):for x in range(n):if (p := pa[x][i]) != -1:pa[x][i + 1] = pa[p][i]self.depth = depthself.pa = padef get_kth_ancestor(self, node: int, k: int) -> int:for i in range(k.bit_length()):if (k >> i) & 1:  # k 二进制从低到高第 i 位是 1node = self.pa[node][i]return node# 返回 x 和 y 的最近公共祖先（节点编号从 0 开始）def get_lca(self, x: int, y: int) -> int:if self.depth[x] > self.depth[y]:x, y = y, x# 使 y 和 x 在同一深度y = self.get_kth_ancestor(y, self.depth[y] - self.depth[x])if y == x:return xfor i in range(len(self.pa[x]) - 1, -1, -1):px, py = self.pa[x][i], self.pa[y][i]if px != py:x, y = px, py  # 同时上跳 2**i 步return self.pa[x][0]