#3367

Maximize Sum of Weights after Edge Removals

international master · 1970 · lc hard +32 · 30.5% accepted · 100 likes · top 8%

Description

An undirected tree with n nodes (numbered 0 to n - 1) is given as a 2D array edges of length n - 1, where edges[i] = [ui, vi, wi] denotes an edge between nodes ui and vi with weight wi.

Remove zero or more edges so that:

- Every node has at most k neighboring edges in the resulting graph.

- The total weight of remaining edges is maximized.

Return the maximum achievable sum of weights.

Code

1

2

3

class Solution:
    def maximizeSumOfWeights(self, edges: List[List[int]], k: int) -> int:

class Solution:
    def maximizeSumOfWeights(self, edges: List[List[int]], k: int) -> int: