Sewer Drainage Partition
A sewer drainage system forms a rooted tree. Water enters at n nodes numbered from 0 to n - 1 and flows upward to the root 0.
The tree is described by parent, where parent[i] = j means water flows from node i to its direct parent j. The root has parent[0] = -1.
input[i] is the amount of water entering directly at node i. The total flow through a node is its own direct input plus the total flows of all of its children.
Cut exactly one branch so the tree is split into two subtrees. Return the minimum possible absolute difference between the total flows of the two resulting parts.
Complete drainagePartition.
drainagePartition has the following parameters:
int[] parent: the parent array describing the rooted treeint[] input: direct inflow at each node
Returns: int minimum absolute difference after cutting one branch.
parent = [-1,0,0,1,1,2] input = [1,2,2,1,1,1] return = 0
Cut the edge between nodes 1 and 0. One component has nodes {0,2,5} with total flow 4, and the other has nodes {1,3,4} with total flow 4. The difference is 0.
parent = [-1,0,1,2] input = [1,4,3,4] return = 2
Cut the edge between nodes 1 and 2. The two resulting parts have total flows 5 and 7, so the minimum difference is 2.
2 <= n <= 10^51 <= input[i] <= 10^4parent[0] = -10 <= parent[i] < ifor1 <= i < n- The tree depth is at most
500.
public int drainagePartition(int[] parent, int[] input) {
// write your code here
}