Maximum Star Sum of a Graph - Detailed Solution C++
Problem UnderstandingIn this problem:
We have an undirected graph with n nodes (0 to n-1)
Each node has a value given in the vals array
A star graph is a subgra
## Problem Understanding

In this problem:
- We have an undirected graph with n nodes (0 to n-1)
- Each node has a value given in the `vals` array
- A star graph is a subgraph with a center node and its neighbors
- We need to find the maximum sum possible from a star graph with at most k edges
- The star sum is the sum of all node values in the star graph (center + selected neighbors)

## Approach: Greedy Selection with Priority Queue

The key insight is that for each potential center node, we want to select up to k neighbors that contribute the highest positive values to our sum.

### Steps:

1. For each node i (potential center):
   - Start with the value of node i
   - Greedily add up to k neighbors with highest positive values
   - Update the maximum star sum seen so far
2. Return the maximum star sum

## Implementation

```cpp
int maxStarSum(vector<int>& vals, vector<vector<int>>& edges, int k) {
    int n = vals.size();
    unordered_map<int, priority_queue<int>> g;
    int maxVal = INT_MIN;
    
    // Build adjacency list with priority queues
    for (auto e : edges) {
        g[e[0]].push(vals[e[1]]);
        g[e[1]].push(vals[e[0]]);
    }
    
    // Check each node as potential center
    for (int i = 0; i < n; i++) {
        int s = vals[i];  // Start with center node's value
        int j = 0;
        
        // Add up to k highest-value neighbors if they increase the sum
        while (j < k && !g[i].empty()) {
            if (g[i].top() > 0) {  // Only add positive values
                s += g[i].top();
                g[i].pop();
            } else {
                break;  // No more positive values to add
            }
            j++;
        }
        
        maxVal = max(maxVal, s);
    }
    
    return maxVal;
}
```

### Key Points:
- We use `priority_queue` (max heap) to efficiently get the highest values first
- We only add neighbors if they have positive values (otherwise they would decrease our sum)
- The initial star sum for each center is just its own value
- We handle the case where a node has no neighbors by starting with just the center's value

## Time and Space Complexity

### Time Complexity: O(E + n * k)
- Building the adjacency list: O(E) where E is the number of edges
- For each of the n nodes, we may extract up to k elements from its priority queue: O(n * k)
- Total: O(E + n * k)

### Space Complexity: O(E)
- The adjacency list (hash map of priority queues) stores all edges, requiring O(E) space

## Related Topics
- Graph
- Greedy
- Priority Queue

## Common Mistakes to Avoid
1. Forgetting that a star graph can have 0 neighbors
2. Adding neighbors with negative values (which would decrease the sum)
3. Not considering all nodes as potential centers

## Edge Cases
- Graph with no edges: The maximum star sum would be the maximum value in the vals array
- Negative values: We should only add neighbors with positive values
- k = 0: The star sum for each center would be just its own value


['Greedy', 'Graph', 'Heap (Priority Queue)', 'C++']