Minimum Root-to-Leaf Cut Cost

You are given a rooted binary tree whose edges have nonnegative integer costs. Choose a set of edges to cut so that the root is disconnected from every leaf of the original tree. Return the minimum possible sum of the cut-edge costs.
The tree is encoded by four arrays of equal length n. Node 0 is the root. For each node i, leftChild[i] and rightChild[i] are its child indices, or -1 when that child is absent. When a child is present, the matching entry in leftCost or rightCost is the cost of that edge; when it is absent, the matching cost is 0.
A leaf is determined from the original tree: it is a node with no children before any cuts. Cutting an edge may disconnect many original leaves at once. Nodes that become leaves only because of earlier cuts do not add new requirements.
If all four arrays are empty, or if the tree contains only its root, return 0.
Interview follow-up
The primary problem requires nonnegative edge costs. With negative costs, an optimal answer may cut extra edges even after a leaf is already disconnected, so the primary recurrence no longer applies unchanged.

Function
minimumRootLeafCutCost(leftChild: List<Integer>, rightChild: List<Integer>, leftCost: List<Integer>, rightCost: List<Integer>) → long

Examples
Example 1
leftChild = [1,3,5,-1,-1,-1,-1]
rightChild = [2,4,6,-1,-1,-1,-1]
leftCost = [4,1,6,0,0,0,0]
rightCost = [7,5,2,0,0,0,0]
return = 11
Below node 1, cutting both leaf edges costs 1 + 5 = 6, so cutting the root-to-1 edge for 4 is cheaper. Below node 2, the leaf edges cost 6 + 2 = 8, so cutting the root-to-2 edge for 7 is cheaper. The minimum total is 4 + 7 = 11.
Example 2
leftChild = [1,2,3,-1]
rightChild = [-1,-1,-1,-1]
leftCost = [8,3,5,0]
rightCost = [0,0,0,0]
return = 3
There is one root-to-leaf path. Cutting its middle edge, from node 1 to node 2, costs 3, which is cheaper than cutting either other edge.
Example 3
leftChild = [-1]
rightChild = [-1]
leftCost = [0]
rightCost = [0]
return = 0
The root-only case has no edge that can be cut, and the required result is 0.

Constraints
0 <= n <= 2147483647
All four arrays have length n.
When n > 0, the child indices form one valid binary tree rooted at node 0: every node other than 0 appears exactly once as a child, and every node is reachable from the root.
Each child index is -1 or lies between 0 and n - 1.
An absent child has matching edge cost 0. A present edge has cost between 0 and 2147483647, inclusive.
The sum of all edge costs is at most 2147483647.

The trick is a post-order recurrence. For a node v, define best(v) as the min cost to disconnect v from all leaves in its subtree. A leaf has no children, so best(leaf) is infinity, since there's nothing below to cut. For each child edge with cost c, the option is min(c, best(child)): either cut this edge, or pay to separate below. Then best(v) is the sum of the options over its present children. The answer is best(root), or 0 for an empty or root-only tree. Pitfalls: treating a leaf as zero cost, which makes everything free, and using plain recursion on a deep tree that overflows the stack, so go iterative. Use a 64-bit sum. Example 2 shows why: the chain picks the cheapest edge, 3. If you freeze on the recurrence in the live OA, StealthCoder is the hedge that gives you the working code.

Memorize the pattern. If you can't, run StealthCoder. The proctor sees the IDE. They don't see what's behind it.