Loading... ```java class TreeAncestor { int[][] pa; int len = 16; public TreeAncestor(int n, int[] parent) { pa = new int[n][len]; for (int i = 0; i < n; i++) { Arrays.fill(pa[i], -1); pa[i][0] = parent[i]; } for (int i = 0; i < len; i++) { for (int k = 0; k < n; k++) { int x = pa[k][i]; if (x != -1) pa[k][i + 1] = pa[x][i]; } } } public int getKthAncestor(int node, int k) { int x = node; for (int i = 0; i < len; i++) { if ((k >> i & 1) != 0) x = pa[x][i]; if (x == -1) break; } return x; } } ``` Last modification：April 6, 2024 © Allow specification reprint Like 0 如果觉得我的文章对你有用，请随意赞赏
Comment here is closed