There is an undirected tree where each vertex is numbered from to , and each contains a data value. The sum of a tree is the sum of all its nodes' data values. If an edge is cut, two smaller trees are formed. The difference between two trees is the absolute value of the difference in their sums.
Given a tree, determine which edge to cut so that the resulting trees have a minimal difference between them, then return that difference.
In this case, node numbers match their weights for convenience. The graph is shown below.
The values are calculated as follows:
Edge Tree 1 Tree 2 Absolute
Cut Sum Sum Difference
1 8 13 5
2 9 12 3
3 6 15 9
4 4 17 13
5 5 16 11
The minimum absolute difference is .
Note: The given tree is always rooted at vertex .
Complete the cutTheTree function in the editor below.
cutTheTree has the following parameter(s):
int data[n]: an array of integers that represent node values
int edges[n-1]: an 2 dimensional array of integer pairs where each pair represents nodes connected by the edge
int: the minimum achievable absolute difference of tree sums
The first line contains an integer , the number of vertices in the tree.
The second line contains space-separated integers, where each integer denotes the data value, .
Each of the subsequent lines contains two space-separated integers and that describe edge in tree .