#3367

Maximize Sum of Weights after Edge Removals

hard · 30.5% accepted · 100 likes · top 8%

dynamic programming · tree · depth-first search · sorting

⊣ practice⊣ open on leetcode ↗

Description

There exists an undirected tree with n nodes numbered 0 to n - 1. You are given a 2D integer array edges of length n - 1, where edges[i] = [ui, vi, wi] indicates that there is an edge between nodes ui and vi with weight wi in the tree.

Your task is to remove zero or more edges such that:

- Each node has an edge with at most k other nodes, where k is given.

- The sum of the weights of the remaining edges is maximized.

Return the maximum possible sum of weights for the remaining edges after making the necessary removals.

Solution