Chương trình tìm tổ tiên thứ K của nút trong cây trong Python

Cho cây n nút (0..n-1) bằng mảng parent (parent[i] là cha của i, gốc là 0). Tìm tổ tiên thứ k của nút node, trả về -1 nếu không tồn tại.

Ví dụ: parent = [-1,0,0,1,2,2,5,5], node=6, k=2 → 2 (cha cấp 1 là 5, cấp 2 là 2).

Giải thuật (Nhảy nhị phân / Binary Lifting)

1. Nếu node == -1: trả về -1.
2. Nếu k == 1: trả về parent[node].
3. Nếu k là lũy thừa của 2 (k & (k-1) == 0):
   • Đệ quy: solve(parent, solve(parent, node, k//2), k//2).
4. Ngược lại: tìm bit cao nhất msb = 1 << (k.bit_length()-1), đệ quy: solve(parent, solve(parent, node, k-msb), msb).

Ví dụ minh họa

def solve(parent, node, k):
    if node == -1:
        return -1
    elif k == 1:
        return parent[node]
    elif not (k & (k-1)):
        return solve(parent, solve(parent, node, k >> 1), k >> 1)
    else:
        msb = 1 << (k.bit_length() - 1)
        return solve(parent, solve(parent, node, k - msb), msb)

parent = [-1,0,0,1,2,2,5,5]
node = 6
k = 2
print(solve(parent, node, k))

Đầu vào

[6,7,9,16,22], 2

Đầu ra

2