We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
n = int(input())
nodes = list(map(int,input().split(' ')))
nodes.insert(0,0)
graph = defaultdict(list)
for _ in range(n-1):
x,y = list(map(int,input().split(' ')))
graph[x].append(y)
graph[y].append(x)
parent = {}
queue = deque([[1,-1]])
while queue:
curr,prev = queue.popleft()
parent[curr] = prev
for nei in graph[curr]:
if nei!=prev:
queue.append([nei,curr])
res = nodes[1]
MOD = 10**9+7
for i in range(2,n+1):
res*=(nodes[i]-nodes[parent[i]])
res%=MOD
print(res)
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Matrix Tree
You are viewing a single comment's thread. Return to all comments →
from collections import *
n = int(input()) nodes = list(map(int,input().split(' '))) nodes.insert(0,0) graph = defaultdict(list) for _ in range(n-1): x,y = list(map(int,input().split(' '))) graph[x].append(y) graph[y].append(x)
parent = {} queue = deque([[1,-1]]) while queue: curr,prev = queue.popleft() parent[curr] = prev for nei in graph[curr]: if nei!=prev: queue.append([nei,curr])
res = nodes[1] MOD = 10**9+7 for i in range(2,n+1): res*=(nodes[i]-nodes[parent[i]]) res%=MOD print(res)