﻿ # 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")
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):
40.     global maxFinal
41.
42.     maxNode = values[start]
43.     for nextNode in connections[start]:
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
54. Maxi(0)
55.
56. file = open("asmax.out", "w")
57. file.write(str(maxFinal))
58. file.close()
RAW Paste Data