本文共 875 字，大约阅读时间需要 2 分钟。

题目：（困难）

标签：树、动态规划

解法一：

class TreeAncestor:    _POW = 16  # 树的最大深度：50000 < 2^16    def __init__(self, n: int, parent: List[int]):        # 初始化状态矩阵        self.dp = [[-1] * self._POW for _ in range(n)]        # 构造初始的父节点关系        for i in range(n):            self.dp[i][0] = parent[i]        # 逐层构造动态规划中的祖先关系        for j in range(1, self._POW):            for i in range(n):                if self.dp[i][j - 1] != -1:                    self.dp[i][j] = self.dp[self.dp[i][j - 1]][j - 1]    def getKthAncestor(self, node: int, k: int) -> int:        for i in range(self._POW - 1, -1, -1):            if k & (1 << i):                node = self.dp[node][i]                if node == -1:                    break        return node

转载地址：https://dataartist.blog.csdn.net/article/details/112465300 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！