Maximum Star Sum of a Graph
There is an undirected graph consisting of n nodes numbered from 0 to n - 1. You are given a 0-indexed integer array vals of length n where vals[i] denotes the value of the i^th node.
You are also given a 2D integer array edges where edges[i] = [ai, bi] denotes that there exists an undirected edge connecting nodes ai and bi.
A star graph is a subgraph of the given graph having a center node containing 0 or more neighbors. In other words, it is a subset of edges of the given graph such that there exists a common node for all edges.
The star sum is the sum of the values of all the nodes present in the star graph.
Given an integer k, return the maximum star sum of a star graph containing at most k edges.
Example 1
Input
vals = [1,2,3,4,10,-10,-20], edges = [[0,1],[1,2],[1,3],[3,4],[3,5],[3,6]], k = 2Output
16The maximum star sum is centered at node 3 and includes neighbors 1 and 4, giving 4 + 2 + 10 = 16.
Example 2
Input
vals = [-5], edges = [], k = 0Output
-5There is only one possible star graph, which is node 0 itself, so the answer is -5.
Constraints
- n == vals.length
- 1 <= n <= 10^5
- -10^4 <= vals[i] <= 10^4
- 0 <= edges.length <= min(n * (n - 1) / 2, 10^5)
- edges[i].length == 2
- 0 <= ai, bi <= n - 1
- ai != bi
- 0 <= k <= n - 1