Best Hub With Spokes

Medium

You have an undirected graph of n nodes numbered 0 to n - 1. Node i is worth values[i], which may be negative. The list links holds the edges: links[j] = [a, b] connects nodes a and b. A **star** is a center node together with any set of its neighbours (possibly none); the edges from the center to the chosen neighbours are its spokes. The worth of a star is the total worth of the center and all chosen neighbours. Return the largest worth of a star with at most max_spokes spokes.

Example 1

values=[4, -1, 7, 3, 2], links=[[0, 1], [0, 2], [0, 3], [3, 4]], max_spokes=2 → 14

Center 0 (value 4) links to 1, 2 and 3. Taking the two best spokes, 7 and 3, gives 4 + 7 + 3 = 14.

Example 2

values=[-6, -2, -9], links=[[0, 1], [1, 2]], max_spokes=2 → -2

All values are negative, so it is best to take no spokes and pick center 1 with value −2.

Example 3

values=[5, 8], links=[], max_spokes=1 → 8

There are no links, so a star is a single node; the best one is 8.

Constraints

1 ≤ n = len(values) ≤ 10⁵
-10⁴ ≤ values[i] ≤ 10⁴
0 ≤ len(links) ≤ min(n·(n − 1)/2, 10⁵)
0 ≤ a, b ≤ n − 1, a ≠ b
Each pair of nodes is linked by at most one edge
0 ≤ max_spokes ≤ n − 1

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy Graph Array Sorting Heap (Priority Queue)

Similar problems

Studios for Recording Sessions Medium Jobs With a Cooldown Medium Spread Out the Labels Medium Cross Out Half the List Medium One Event per Day Medium

Input

values=[4, -1, 7, 3, 2], links=[[0, 1], [0, 2], [0, 3], [3, 4]], max_spokes=2

Expected

Run checks the first 3 tests in your browser. Submit checks all 104 tests on the server, hidden ones included.