স্পেশাল ম্যাট্রিক্সের ডিটারমিন্যান্ট বের করার প্রোগ্রাম

n ভের্টেক্সের একটি ট্রি দেওয়া আছে, প্রতিটি ভের্টেক্স 1 থেকে n লেবেল করা। রুট হলো ১। প্রতিটি ভের্টেক্সের ওজন wi। একটি n×n ম্যাট্রিক্স A তৈরি হয় যেখানে A(x,y) = W_{f(x,y)} এবং f(x,y) হলো x এবং y-এর লিস্ট কমন প্রিডিসেসর (LCA)। এডজ, ওজন এবং ভের্টেক্স সংখ্যা ইনপুট হিসেবে দেওয়া আছে। ম্যাট্রিক্স A-এর ডিটারমিন্যান্ট বের করতে হবে।

ইনপুট: edges = [[1,2],[1,3],[1,4],[1,5]], weights = [1,2,3,4,5], vertices = 5 → আউটপুট: 24।

ম্যাট্রিক্স A:

1	1	1	1	1
1	2	1	1	1
1	1	3	1	1
1	1	1	4	1
1	1	1	1	5

ডিটারমিন্যান্ট = ২৪।

সমাধানের ধাপসমূহ (DFS + স্ট্যাক)

w := প্রতিটি ভের্টেক্সের জন্য [weight, children_list]
এডজ লিস্ট থেকে ট্রি বানান
det := 1, stack := [(0, 0)]
যখন stack খালি নয়:
- i, weights = stack.pop()
- det = (det * (w[i][0] - weights)) % (10⁹+7)
- w[i][1]-এর প্রতিটি t-এর জন্য: stack.append((t, w[i][0]))
- w[i][1]-এর প্রতিটি t-এর জন্য: w[t][1].remove(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