FastPrep
Problem · Tree

The Crazy Ruler

Learn this problem
● MediumMicrosoft logoMicrosoftOA
See Microsoft hiring insights

Problem statement

A connected country contains N cities numbered from 1 to N. Its N - 1 roads form a tree. City i has satisfaction value A[i].

The king evaluates one connected country by taking every distinct satisfaction value that appears in it exactly once and summing those distinct values.

Remove exactly one road to split the tree into two connected countries. Maximize the sum of the king's evaluations of the two resulting countries.

Return the maximum value modulo 10^9 + 7.

Function

maxSatisfactionSum(A: int[], edges: int[][]) → int

Examples

Example 1

A = [2, 3, 2, 10, 10]edges = [[1, 4], [4, 3], [4, 2], [1, 5]]return = 27
Removing road (1, 4) creates components with distinct-value sums 12 and 15. Their combined evaluation is 27.

Example 2

A = [2, 2, 3, 2, 10, 3]edges = [[1, 4], [4, 3], [4, 2], [1, 5], [5, 6]]return = 20
Removing road (1, 4) produces distinct-value sets {2, 3, 10} and {2, 3}. Their sums are 15 and 5, for a total of 20.

Example 3

A = [1, 2, 2, 1, 2, 1, 2]edges = [[1, 4], [3, 2], [2, 7], [4, 2], [1, 5], [5, 6]]return = 6
Removing road (1, 5) makes both components contain distinct values {1, 2}. Each evaluates to 3, so the answer is 6.

Constraints

  • 2 ≤ N ≤ 10^5
  • edges.length = N - 1
  • 1 ≤ U, V ≤ N
  • 1 ≤ A[i] ≤ 10^5

More Microsoft problems

drafts saved locally
public int maxSatisfactionSum(int[] A, int[][] edges) {
    // write your code here
}
A[2, 3, 2, 10, 10]
edges[[1, 4], [4, 3], [4, 2], [1, 5]]
expected27
checking account