本质：DP的思想

1483. 树节点的第 K 个祖先

给你一棵树，树上有 n 个节点，按从 0 到 n-1 编号。树以父节点数组的形式给出，其中 parent[i] 是节点 i 的父节点。树的根节点是编号为 0 的节点。
树节点的第 k 个祖先节点是从该节点到根节点路径上的第 k 个节点。
实现 TreeAncestor 类：

  • TreeAncestor（int n， int[] parent） 对树和父数组中的节点数初始化对象。
  • getKthAncestor(int node, int k) 返回节点 node 的第 k 个祖先节点。如果不存在这样的祖先节点，返回 -1 。

示例 1：
image.png
输入： [“TreeAncestor”,”getKthAncestor”,”getKthAncestor”,”getKthAncestor”] [[7,[-1,0,0,1,1,2,2]],[3,1],[5,2],[6,3]] 输出： [null,1,0,-1] 解释： TreeAncestor treeAncestor = new TreeAncestor(7, [-1, 0, 0, 1, 1, 2, 2]); treeAncestor.getKthAncestor(3, 1); // 返回 1 ，它是 3 的父节点 treeAncestor.getKthAncestor(5, 2); // 返回 0 ，它是 5 的祖父节点 treeAncestor.getKthAncestor(6, 3); // 返回 -1 因为不存在满足要求的祖先节点

提示：

  • 1 <= k <= n <= 5 * 104
  • parent[0] == -1 表示编号为 0 的节点是根节点。
  • 对于所有的 0 < i < n ，0 <= parent[i] < n 总成立
  • 0 <= node < n
  • 至多查询 5 * 104 次

思路：
倍增思想
直接遍历寻找每个节点的祖先会超时
已知：当前节点父节点的父节点是当前节点的二代祖先
故可以使用倍增的思想，用父节点的一代祖先更新当前节点的二代祖先
以此类推，用当前节点的二代祖先的二代祖先更新当前节点的四代祖先
。。。
本质是一种DP

查询时：利用log的乘法变加法运算，快速找到当前节点的k代祖先

  1. class TreeAncestor {
  2.     int N = 20;
  3.     int[][] root;
  4.     int n;
  5.     public TreeAncestor(int n, int[] parent) {
  6.         this.n = n;
  7.         root = new int[n][N];
  8.         for (int i = 0; i < n; i++)
  9.             Arrays.fill(root[i], -1);
  11.         for (int i = 0; i < n; i++) {
  12.             root[i][0] = parent[i];
  13.         }
  15.         for (int j = 1; j < N; j++) {
  16.             for (int i = 0; i < n; i++) {
  17.                 int fa = root[i][j - 1];
  18.                 if (fa != -1) {
  19.                     root[i][j] = root[fa][j - 1];
  20.                 }
  21.             }
  22.         }
  23.     }
  25.     public int getKthAncestor(int node, int k) {
  27.         for (int i = 0; i < N; i++) {
  28.             if ((k >> i & 1) == 1) {
  29.                 node = root[node][i];
  30.                 if (node == -1)
  31.                     break;
  32.             }
  33.         }
  34.         return node;
  35.     }
  36. }
  38. /**
  39.  * Your TreeAncestor object will be instantiated and called as such:
  40.  * TreeAncestor obj = new TreeAncestor(n, parent);
  41.  * int param_1 = obj.getKthAncestor(node,k);
  42.  */

异曲同工：
1483的解题步骤中有这样一步，之前算过的内容在之后会被用到
类似的问题有AcWing 1295. X的因子链，在分解质因数时，如果提前预处理了线性筛，可以在logn的时间复杂度内求出x的算术基本定理的结果。