Chương trình Python tìm định thức của ma trận đặc biệt

Giả sử ta có cây với n đỉnh, mỗi đỉnh nhãn từ 1 đến n. Gốc cây nhãn 1, mỗi đỉnh có trọng số w_i. Ma trận n x n A với A(x,y) = W_{f(x,y)} trong đó f(x,y) là tổ tiên chung gần nhất (LCA) của đỉnh x và y. Tìm định thức của ma trận A. Các cạnh, trọng số và số đỉnh được cho.

Ví dụ: input_array = [[1,2],[1,3],[1,4],[1,5]], weights = [1,2,3,4,5], vertices = 5, kết quả là 24.

Ma trận A:

Định thức = 24.

Giải thuật

1. w := []
2. For i từ 0 đến vertices: thêm [weights[i], []] vào w
3. For i, item trong input_array:
   • p := item[0], q := item[1]
   • Thêm q-1 vào w[p-1][1], thêm p-1 vào w[q-1][1]
4. det := 1
5. stack := [(0, 0)]
6. While stack không rỗng:
   • i, weights := stack.pop()
   • det := (det * (w[i][0] - weights)) % (10^9 + 7)
   • For t trong w[i][1]:
     • Thêm (t, w[i][0]) vào stack
   • For t trong w[i][1]: xóa i khỏi w[t][1]
7. Trả về det

Ví dụ

def solve(input_array, weights, vertices):
    w = [[weights[i], []] for i in range(vertices)]
    for i, item in enumerate(input_array):
        p, q = item[0], item[1]
        w[p - 1][1].append(q - 1)
        w[q - 1][1].append(p - 1)
    det = 1
    stack = [(0, 0)]
    while stack:
        i, weights = stack.pop()
        det = (det * (w[i][0] - weights)) % (10**9 + 7)
        stack += [(t, w[i][0]) for t in w[i][1]]
        for t in w[i][1]:
            w[t][1].remove(i)
    return det

print(solve([[1, 2], [1, 3], [1, 4], [1, 5]], [1, 2, 3, 4, 5], 5))

Input

[[1, 2], [1, 3], [1, 4], [1, 5]], [1, 2, 3, 4, 5], 5

Output

24