Maximum-Sum Star with at Most K Arms

Given a simple undirected graph with an integer value on each node and an integer k, return the largest node-value sum of any nonempty star subgraph with at most k arms.

A star has one center and zero or more distinct neighbors selected as leaves. Each selected leaf must be joined to the center by a graph edge. A center alone is a valid star. Count each selected node's value once. The chosen star is a subgraph: any edges between selected leaves need not be included.

Function and Inputs

Complete bestSumKStar(g_nodes, g_from, g_to, values, k):

• g_nodes is the number of nodes, labeled 0 through g_nodes - 1.
• g_from and g_to are equally sized arrays. Edge i joins g_from[i] and g_to[i].
• values[i] is the integer value of node i.
• k is the maximum number of arms in the star.

Return one integer: the maximum sum among all allowed stars.

Constraints

• 2 <= g_nodes <= 100000 and 1 <= g_edges <= 100000, where g_edges is the length of each edge array.
• Every edge endpoint is a valid node label. The graph has no self-loops and at most one edge between a pair of nodes.
• values has length g_nodes, and -1000 <= values[i] <= 1000.
• 0 <= k <= 100000. The graph need not be connected.

Example 1

g_nodes = 4
g_from = [0, 0, 0]
g_to = [1, 2, 3]
values = [5, 4, -2, 3]
k = 2
answer = 12

The star centered at node 0 with leaves 1 and 3 has sum 5 + 4 + 3 = 12.

Example 2

g_nodes = 2
g_from = [0]
g_to = [1]
values = [-4, -1]
k = 1
answer = -1

The valid star containing only node 1 has sum -1.