Problem Brief

Sewer Drainage Partition

FULLTIMEOA

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.

Function Description

Complete drainagePartition.

drainagePartition has the following parameters:

int[] parent: the parent array describing the rooted tree
int[] input: direct inflow at each node

Returns: int minimum absolute difference after cutting one branch.

1Example 1

Input

parent = [-1,0,0,1,1,2], input = [1,2,2,1,1,1]

Output

Explanation

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.

2Example 2

Input

parent = [-1,0,1,2], input = [1,4,3,4]

Output

Explanation

Cut the edge between nodes 1 and 2. The two resulting parts have total flows 5 and 7, so the minimum difference is 2.

Constraints

Limits and guarantees your solution can rely on.

2 <= n <= 10^5
1 <= input[i] <= 10^4
parent[0] = -1
0 <= parent[i] < i for 1 <= i < n
The tree depth is at most 500.