Choose a Center and up to k Neighbors for Maximum Star Value
Company: Akuna Capital
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
In the undirected graph `edges`, a star contains one center node and any subset of its neighbors using at most k incident edges. Its value is the sum of the values of its included nodes. Return the greatest possible star value, permitting the center alone.
```cpp
class Solution {
public:
int maxStarSum(vector<int>& vals, vector<vector<int>>& edges, int k);
};
```
### Examples
**Example 1:**
```text
Input: vals = [-2,5,4], edges = [[0,1],[0,2]], k = 2
Output: 7
Explanation: Center0 with both neighbors totals-2+5+4=7, beating centers 1 and 2 with their negative neighbor omitted.
```
**Example 2:**
```text
Input: vals = [-3,-1], edges = [[0,1]], k = 1
Output: -1
Explanation: Select node 1 alone; adding its negative neighbor would reduce the sum.
```
### Constraints
- `1 <= n == vals.length <= 100000`; `-10000 <= vals[i] <= 10000`.
- `0 <= edges.length <= min(n*(n-1)/2,100000)`.
- Each edge joins distinct labels in[0, n-1].
- `0 <= k <= n-1`.
### Clarifying Questions
- Must exactly `k` edges be chosen? No; choose at most k.
- Can a star contain only its center? Yes.
- Can the best sum be negative? Yes; a center must still be selected.
- Can a neighbor’s value be counted twice through repeated edge copies? No; a star sums included nodes.
```hint Check the boundary
Check `k = 0` and a graph where every node value is negative.
```
Overview: Choose a center and at most k neighboring nodes for the greatest star sum, allowing the center alone and negative results.