Python 3 DFS solution Time:O(n)


#1
maxi = 0
sumA = 0
def dfs(curr,A,adj,visited):
    global maxi,sumA

    for i in range(len(adj[curr])):
        value = adj[curr][i]
        if visited[value] == 0:
            visited[value] = 1
            ret = dfs(value,A,adj,visited)
            A[curr-1] += ret
            visited[value] = 0
    maxi = max(maxi,(A[curr-1]*(sumA-A[curr-1]))%1000000007)
    return A[curr-1]

class Solution:
    # @param A : list of integers
    # @param B : list of list of integers
    # @return an integer
    def deleteEdge(self, A, B):
        visited = [0]*(len(A)+1)
        global maxi,sumA
        sumA = sum(A)
        maxi = 0
        adj_list = {}
        for i in B:
            adj_list[i[0]] = adj_list.get(i[0],[]) + [i[1]]
            adj_list[i[1]] = adj_list.get(i[1],[]) + [i[0]]
        visited[1] =1
        dfs(1,A,adj_list,visited)
        return maxi