Problem 2 Science Challenge

#Statement :
#Let there be an undirected connected acyclic graph (I.E. a tree) with N nodes, in which every node i has an integer value Vi.
#We define a subtree of our tree to be a nonzero connected subgraph of it (which can also be the initial tree). Your task is to determine a subtree of a given tree, for which the sum of the values of its nodes is maximal.
#INPUT :
#   N, representing the number of nodes of your tree
#   N integers, the i'th integer representing V the next N-1 lines each contain 2 integers A and B, representing an edge between the node A and the node B
#OUTPUT :
#   One integer S representing the maximal sum of a subtree
#
#Example test :
#>>>5
#>>>-1 1 3 1 -1
#>>>4 1
#>>>1 3
#>>>1 2
#>>>4 5
#5




file = open("asmax.in", "r")
data = file.read().split("\n")
file.close()
data.reverse()

input = data.pop()

nbNodes = int(input())
values = list(map(int, input().split()))
connections = [[] for i in range(nbNodes)]
for iconnection in range(nbNodes-1):
    node1, node2 = map(int, input().split())
    connections[node1-1].append(node2-1)
    connections[node2-1].append(node1-1)


def Maxi(start):
    global alreadyDone
    global maxFinal

    maxNode = values[start]
    for nextNode in connections[start]:
        if not(alreadyDone[nextNode]):
            alreadyDone[nextNode] = True
            maxNode += max(0, Maxi(nextNode))

    maxFinal = max(maxFinal, maxNode)
    return maxNode


alreadyDone = [False for i in range(nbNodes)]
maxFinal = values[0]
Maxi(0)

file = open("asmax.out", "w")
file.write(str(maxFinal))
file.close()