The Crazy Ruler

Problem Overview

• Given a country with N cities (tree) and array A of satisfaction levels, remove one edge to split it into two parts maximizing the sum of each part’s total satisfaction.
• Input: N, N-1 edges, and N values A[i]. Output: maximum combined evaluation modulo 1e9+7. Constraints: N≤1e5, A[i]≤1e9.
• Real-world context: a ruler gauges each region by the sum of its cities’ satisfaction after the split.
• From Microsoft interviews; a coding interview problem and interview question on tree partitioning.