Minimum-Sum Tree Fill with Unit Steps
Problem statement
A tree has n nodes numbered 0 to n - 1, connected by the undirected edges in edges. Some nodes already have a value: if values[i] is not -1, node i must keep exactly that value. A value of -1 means node i is empty and must be filled.
Fill every empty node with a non-negative integer so that the two ends of every edge differ by exactly 1. Among all valid fillings, find the smallest possible sum of all n values (known and filled).
Return that smallest sum, or -1 if no valid filling exists. The sum can exceed the 32-bit integer range.
Function
minimumFilledSum(n: int, edges: int[][], values: int[]) → longExamples
Example 1
n = 6edges = [[0,1],[1,2],[1,3],[3,4],[3,5]]values = [-1,-1,5,-1,2,-1]return = 19- Node
2is known to be5and node4is known to be2. They are three edges apart (2 - 1 - 3 - 4) and differ by3, so the path between them must step down by one each time: node1is4and node3is3. - Node
0is next to node1(value4), so it is3or5; the smaller choice3is best. - Node
5is next to node3(value3), so it is2or4; choose2. - The total is
3 + 4 + 5 + 3 + 2 + 2 = 19.
Example 2
n = 3edges = [[0,1],[1,2]]values = [0,-1,3]return = -1Nodes 0 and 2 are two edges apart, so their values can differ by at most 2. They differ by 3, so no filling works and the answer is -1.
Example 3
n = 5edges = [[0,1],[0,2],[0,3],[0,4]]values = [-1,1,-1,-1,-1]return = 4- Node
1is1, so the center node0is0or2. Choose0. - Each other leaf is next to the center, so it must be
1: the value-1is not allowed because filled values cannot be negative. - The total is
0 + 1 + 1 + 1 + 1 = 4.
Constraints
1 <= n <= 5000edges.length == n - 1, each edge is[u, v]with0 <= u, v < nandu != v, and the edges form a tree.values.length == n- Each
values[i]is-1or satisfies0 <= values[i] <= 10^9. - At least one
values[i]is not-1.