Edge cutting in Trees

Question

A tree can be split into two different trees by removing one of its edges. Given a tree with N nodes uniquely identified by integer numbers in the [0, N-1] range, I need to write a function that finds the edge that needs to be removed from the tree, such that the difference between the sums of all the node IDs in the resulting trees is minimized.

The function should print the minimum difference that it found to the standard output (stdout).

The function will receive the following arguments:

parent which is an array of integer numbers with the following meaning: parent[i] = the parent of node i (more specifically its ID)

parent[i] = -1 if i has no parent (i is the root of the tree)

Data constraints

The maximum number of nodes in the tree is 50,000

Efficiency constraints

The function is expected to print the result in less than 2 seconds

Example

 Input parent: [1, 4, 4, 2, -1, 2, 2]

 aka :         4
              / \
             1   2
            /  / | \
           0  3  5  6   

 Output: 9

Explanation: We remove the edge between nodes 2 and 6.

Answer 1

1. For each node, compute the sum of its children, then add this value to itself, and store it in the node. Let's call this value S_n where n is a node. (Can be done easily by recursion & post-order traversal)

2. Find the node n which S_n has minimum difference to to S_root/2. The edge between n and its parent is the edge we want. (This requires linear time in worst case.)