Beats 99.18% | Simple Solution w/ explanation | T:O(m log k), S:O(n + m)
Intuition\nThe problem asks us to find the maximum possible star sum in a graph, where a star is a subgraph with a central node connected to its neighbors. The 
# Intuition\nThe problem asks us to find the maximum possible star sum in a graph, where a star is a subgraph with a central node connected to its neighbors. The challenge is to pick the `k` largest neighbors to maximize the sum of node values.\n\nInitially, we might think of sorting all neighbors for each node and selecting the top `k`. However, sorting the entire list of neighbors is inefficient because we only need the largest `k` values. Instead, we can use a **heap** to maintain the top `k` neighbors dynamically as we process each node\'s neighbors, avoiding the need to sort them all.\n\n# Approach\n1. **Graph Construction**: Build an adjacency list from the input edges, where each node points to a list of its neighbors.\n2. **Heap for Efficient Neighbor Selection**: For each node, use a **min-heap** to keep track of the top `k` largest positive neighbor values. As we iterate through the neighbors of each node, push their values into the heap. If the size of the heap exceeds `k`, pop the smallest value, ensuring that the heap only contains the largest `k` values.\n3. **Calculate the Star Sum**: For each node, the star sum is the node\'s own value plus the sum of the values in the heap (which holds up to `k` positive neighbor values).\n4. **Maximization**: Track the maximum star sum across all nodes and return the result.\n\n### Key Observations:\n- If `k == 0`, the maximum star sum is simply the maximum value in the `vals` array, as no neighbors can be selected.\n- If there are no edges, the same result applies because no neighbors exist.\n\n# Complexity\n- **Time Complexity**: \n  - **O(n + m log k)**, where `n` is the number of nodes and `m` is the number of edges. We iterate over all edges and maintain a heap of size at most `k` for each node.\n  \n- **Space Complexity**: \n  - **O(n + m)**, where `n` is the space for storing the graph and `m` is the space required for the heap and graph traversal.\n\n# Code\n```python3 []\nfrom collections import defaultdict\nimport heapq\n\nclass Solution:\n    def maxStarSum(self, vals: List[int], edges: List[List[int]], k: int) -> int:\n        # Step 1: Build the graph using a dictionary where keys are nodes and values are neighbors\n        dic = defaultdict(list)\n        for a, b in edges:\n            dic[a].append(b)\n            dic[b].append(a)\n\n        max_v = float(\'-inf\')\n        \n        # Step 2: Handle the case when k == 0 or there are no edges\n        if k == 0 or not edges:\n            return max(vals)\n\n        # Step 3: For each node, calculate the maximum star sum\n        for e in range(len(vals)):\n            # Get the neighbors of the node\n            neighbors = dic[e]\n\n            # Step 4: Use a min-heap to maintain the top `k` largest positive neighbors\n            heap = []\n            for neighbor in neighbors:\n                if vals[neighbor] > 0:  # Only consider positive values\n                    # Push the neighbor\'s value to the heap (as negative for a max-heap behavior)\n                    heapq.heappush(heap, vals[neighbor])\n                    if len(heap) > k:\n                        heapq.heappop(heap)  # Remove the smallest if we exceed `k` elements\n\n            # Step 5: Calculate the star sum (the value of the node + the sum of the top `k` neighbors)\n            max_e = vals[e] + sum(heap)\n\n            # Step 6: Update the maximum star sum\n            max_v = max(max_v, max_e)\n\n        return max_v\n```
['Python3']