fingerdash2004

Problem 2 Science Challenge

Jan 12th, 2021 (edited)
385
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #Statement :
  2. #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.
  3. #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.
  4. #INPUT :
  5. #   N, representing the number of nodes of your tree
  6. #   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
  7. #OUTPUT :
  8. #   One integer S representing the maximal sum of a subtree
  9. #
  10. #Example test :
  11. #>>>5
  12. #>>>-1 1 3 1 -1
  13. #>>>4 1
  14. #>>>1 3
  15. #>>>1 2
  16. #>>>4 5
  17. #5
  18.  
  19.  
  20.  
  21.  
  22. file = open("asmax.in", "r")
  23. data = file.read().split("\n")
  24. file.close()
  25. data.reverse()
  26.  
  27. input = data.pop()
  28.  
  29. nbNodes = int(input())
  30. values = list(map(int, input().split()))
  31. connections = [[] for i in range(nbNodes)]
  32. for iconnection in range(nbNodes-1):
  33.     node1, node2 = map(int, input().split())
  34.     connections[node1-1].append(node2-1)
  35.     connections[node2-1].append(node1-1)
  36.  
  37.  
  38. def Maxi(start):
  39.     global alreadyDone
  40.     global maxFinal
  41.  
  42.     maxNode = values[start]
  43.     for nextNode in connections[start]:
  44.         if not(alreadyDone[nextNode]):
  45.             alreadyDone[nextNode] = True
  46.             maxNode += max(0, Maxi(nextNode))
  47.  
  48.     maxFinal = max(maxFinal, maxNode)
  49.     return maxNode
  50.  
  51.  
  52. alreadyDone = [False for i in range(nbNodes)]
  53. maxFinal = values[0]
  54. Maxi(0)
  55.  
  56. file = open("asmax.out", "w")
  57. file.write(str(maxFinal))
  58. file.close()
RAW Paste Data