FastPrep
Problem · Tree

Divide Tree Nodes

Learn this problem
● HardGoogleFULLTIMEOA
See Google hiring insights

Problem statement

You are given an undirected tree with n nodes. Node x has value A[x].

Partition the nodes into the minimum possible number of groups such that no two adjacent nodes belong to the same group.

For a pair of nodes (u, v) in one group, its value is |A[u] - A[v]|. The cost of a group is the maximum total pair value obtainable by pairing nodes in that group, where every node may be used in at most one pair and some nodes may remain unpaired.

Return the sum of the costs of all groups in the minimum-group partition.

Function

divideTreeNodes(n: int, A: int[], edges: int[][]) → long

Examples

Example 1

n = 5A = [12, 17, 14, 13, 16]edges = [[1, 2], [1, 3], [1, 5], [2, 4]]return = 4

One minimum-group partition is {1,4} and {2,3,5}. Their maximum pairing costs are |12-13| = 1 and |17-14| = 3, so the answer is 1 + 3 = 4.

Constraints

  • 1 ≤ T ≤ 10
  • 1 ≤ N ≤ 105
  • 1 ≤ A[i] ≤ 109
  • 1 ≤ U, V ≤ N

More Google problems

drafts saved locally
public long divideTreeNodes(int n, int[] A, int[][] edges) {
  // write your code here
}
n5
A[12, 17, 14, 13, 16]
edges[[1, 2], [1, 3], [1, 5], [2, 4]]
expected4
checking account