SWE / QSE OA — Sewer Tree Partition

Given a rooted tree encoded by parent pointers and per-node input values, cut one edge / node partition so the absolute difference between the two resulting component sums is minimized. Requirements Input includes a parent array and a value array such as inputs. Example described by a candidate: parent = [-1, 0, 0, 1, 1, 2], inputs = [1, 2, 2, 1, 1, 1], return 0, because cutting between node 0 and node 1 creates components {0, 2, 5} and {1, 3, 4} with equal total input sum 4. Implement a function that returns the minimum possible absolute difference between the sums of the two partitions. Notes Model the parent array as a rooted tree, compute subtree sums with DFS, and compare abs(total_sum - 2 * subtree_sum) for each possible cut. Candidates describe this as graph / BFS / DFS style, but the tree invariant makes a single subtree-sum pass sufficient. Clarify whether cutting the root is allowed; in the natural version, only non-root edges are valid cuts. Preparation Write parent-array-to-children-list conversion without mistakes. Drill postorder DFS subtree-sum computation and keep the global best difference. Test single child, balanced split, all positive values, and skewed-tree cases.