与えられた特別な行列の行列式を見つけるためのPythonプログラム

n個の頂点を持つツリーがあり、各頂点に1からnまでのラベルが付けられているとします。ツリーのルートにはラベル1があり、各頂点の重みはwiです。ここで、nxn行列Aが形成されます。ここで、A（x、y）=Wf（x、y）ここで、f（x、y）は頂点xおよびyの最も一般的でない先行です。行列Aの行列式を見つける必要があります。行列のエッジ、重み、および頂点の総数が入力として提供されます。

したがって、入力がinput_array =[[1、2]、[1、3]、[1、4]、[1、5]]のようである場合、重み=[1、2、3、4、5]、頂点=5の場合、出力は24になります。

行列Aは次のように与えられます=

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

これを解決するには、次の手順に従います-

• w：=空のリスト
• 0から頂点までの範囲のiについては、
  • ウェイト[i]と新しいリストをwに追加
• iごとに、enumerate（input_array）の項目を実行します
  • p：=item [0]
  • q：=item [1]
  • w [p-1、1]の最後にq-1を挿入します
  • w [q-1、1]の最後にp-1を挿入します
• det：=1
• stack：=タプル（0、0）を含むスタック
• スタックが空でない間は、
  • i、weights：=スタックから最上位の要素を削除します
  • det：=（det *（w [i、0]-重み））mod（10 ^ 9 + 7）
  • w [i] [1]のtについては、
    • （t、w [i、0]）を含むタプルをスタックに追加します
    • w [i] [1]の各tについて、
      • w [t、1]からiを削除します
• return det

例

理解を深めるために、次の実装を見てみましょう-

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