#3367
Maximize Sum of Weights after Edge Removals
hard · 30.5% accepted · 100 likes · top 8%
dynamic programming · tree · depth-first search · sorting
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