Divide Tree Nodes

Problem Overview

• Partition a tree into the fewest groups so no adjacent nodes share a group; in each group, make disjoint pairs maximizing sum of |A[u]-A[v]|; return the total over all groups.
• Input: T test cases; each has N, values A[1..N], and N-1 edges. Output one total cost per test case.
• Constraints: T≤10, N≤1e5, A[i]≤1e9, nodes labeled 1..N.
• Domain: tree/graph grouping and pairing cost aggregation.
• Source: Google interviews; a coding interview problem and interview question.