โจทย์
มี Tree n จุดยอด (1 ถึง n) Root = 1 น้ำหนักจุดยอด w_i สร้าง Matrix n×n ที่ A(x,y) = W_f(x,y) โดย f(x,y) = LCA (Lowest Common Ancestor) ของ x และ y หา Determinant ของ Matrix A
ตัวอย่าง: Edges [[1,2],[1,3],[1,4],[1,5]], Weights [1,2,3,4,5], n=5 → Matrix แสดงในโจทย์ → Det = 24
อัลกอริธึม (DFS + Stack)
- สร้าง Adjacency List จาก Edges
- DFS แบบ Stack คำนวณ Determinant แบบ Multiplicative
- ใช้สูตร:
det = Π (w[node] - w[parent])mod 1e9+7
โค้ด 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_val = stack.pop()
det = (det * (w[i][0] - weights_val)) % (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)) # Output: 24
Input / Output
Input: [[1,2],[1,3],[1,4],[1,5]], [1,2,3,4,5], 5
Output: 24
