Pythonで木構造から生成される特別な行列の行列式を求める方法

n 個の頂点を持つ木を考えます。各頂点には 1 から n までの番号が付いており、根は頂点 1 です。さらに、各頂点には重み wi が割り当てられています。この木から n×n の行列 A を次のように作成します。A(x, y) = Wf(x, y)。ここで f(x, y) は頂点 x と y の最小共通祖先(LCA)を表します。この問題の目的は、行列 A の行列式を求めることです。木の辺の情報、各頂点の重み、頂点の総数が入力として与えられます。

たとえば、input_array = [[1, 2], [1, 3], [1, 4], [1, 5]]、weights = [1, 2, 3, 4, 5]、vertices = 5 という入力が与えられた場合、出力は 24 になります。

このとき、行列 A は次のようになります。

この行列の行列式は 24 です。

解法の考え方

一見すると、行列式の一般的な計算には O(n³) の時間がかかるように思えます。しかし、この行列には重要な性質があります。行列式は、各頂点 v について「その頂点の重みから親の重みを引いた値」をすべて掛け合わせたものと等しくなります。数式で表すと次の通りです。

det(A) = ∏_v (w(v) − w(parent(v)))

根の親の重みは 0 として扱うため、先ほどの例では 1 × (2−1) × (3−1) × (4−1) × (5−1) = 1 × 1 × 2 × 3 × 4 = 24 となり、答えと一致します。この性質を利用すれば、DFS(深さ優先探索)で木を一度たどるだけで O(n) で行列式を計算できます。

アルゴリズムの手順

• 空のリスト w を用意する。
• i を 0 から vertices−1 まで繰り返し、w に [weights[i], [](重みと隣接リストのペア)] を追加する。
• input_array の各辺 (p, q) について、w[p−1] の隣接リストに q−1 を、w[q−1] の隣接リストに p−1 を追加する。
• det := 1 とし、スタックにタプル (0, 0)(頂点インデックス, 親の重み)を積む。
• スタックが空になるまで、以下を繰り返す。
  • スタックから (i, weights) を取り出す。
  • det := (det × (w[i][0] − weights)) mod (10⁹ + 7) を計算する。
  • w[i] の隣接リスト内の各頂点 t について、(t, w[i][0]) をスタックに積む。同時に、w[t] の隣接リストから i を削除し、子方向へのみ探索が進むようにする。
• det を返す。

実装例

以下の Python コードで実際の動作を確認できます。

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))

入力

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

出力

24

まとめ

最小共通祖先を用いて構成される特殊な行列でも、木構造の性質を活かせば行列式を高速に求められます。ポイントは「各頂点の重みから親の重みを引いた値の積が行列式に等しい」という性質を見抜くことです。DFS を使ったこの実装により、大きな n に対しても効率的に計算できます。