795. Brightest Star
An observatory records n stars, numbered 0 to n - 1; star i has brightness values[i], which may be negative. Each entry [a, b] in edges means stars a and b are linked in the sky chart, and no pair is linked twice.
A constellation picks one hub star and then at most k of the stars linked directly to the hub. It may also have no linked stars at all. Its score is the sum of the brightness of the hub and every chosen linked star. Return the largest score any constellation can reach.
Example 1
- Input:
- values = [4,-2,7,3,5]edges = [[0,1],[0,2],[0,3],[2,4],[3,4]]k = 2
- Output:
- 16
- Explanation:
Centering at node 2 (brightness 7) and taking its two neighbours 0 (4) and 4 (5) gives 16; no other star beats it.
Example 2
- Input:
- values = [-3,-1,-5], edges = [[0,1],[1,2]], k = 2
- Output:
- -1
- Explanation:
Every brightness is negative, so the best star is node 1 alone with brightness -1.
Example 3
- Input:
- values = [2,9,1], edges = [[0,1],[1,2]], k = 0
- Output:
- 9
- Explanation:
With no leaves allowed, the answer is the brightest single node, 9.
Constraints
- 1 ≤ n ≤ 105
- -104 ≤ values[i] ≤ 104
- 0 ≤ edges.length ≤ 105
- 0 ≤ a, b < n, a ≠ b, and no duplicate links
- 0 ≤ k ≤ 105
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 200 msC++ 50 msJava 100 msJavaScript 100 msTypeScript 100 ms
Expected complexity
- Time
- O((n + m) log n)
- Space
- O(n + m)