Maximize Retained Tree Edge Weight with a Degree Limit

### Problem You are given an undirected tree with `n` nodes labeled `0` through `n - 1`. Each row of `edges` is `[u, v, w]`, describing an edge of weight `w` between nodes `u` and `v`. Remove zero or more edges so that every node is incident to at most `k` remaining edges. Return the largest possible sum of the remaining edge weights. The remaining graph need not be connected. Return only the maximum sum, not the removed edges. ```cpp class Solution { public: long long maximizeSumOfWeights(vector<vector<int>>& edges, int k); }; ``` ### Examples **Example 1:** ```text Input: edges = [[0,1,8],[1,2,9],[1,3,7],[3,4,10]], k = 1 Output: 19 Explanation: Keep edges [1,2,9] and [3,4,10]. They share no endpoint, so every degree is at most 1. At most two edges can remain on five nodes with this degree limit; the two largest edge weights sum to 19 and are achievable together. ``` **Example 2:** ```text Input: edges = [[0,1,5],[0,2,4],[0,3,3]], k = 2 Output: 9 Explanation: Keep the edges of weights 5 and 4. All three edges meet node 0, so at least one must be removed. Removing the smallest loses only 3 from the total of 12. ``` ### Constraints - `2 <= n <= 100000`. - `1 <= k <= n - 1`. - `edges.length == n - 1`. - Each edge contains exactly three integers `[u, v, w]`. - `0 <= u, v < n`. - `1 <= w <= 1000000`. - The input edges form a valid tree. ### Clarifying Questions - Does the degree limit apply to every node? Yes, including both endpoints of every retained edge. - Must exactly `k` edges touch each node? No. The limit is at most `k`. - Can all original edges be kept? Yes, if they already satisfy the limit. - Are disconnected components allowed after removals? Yes; their retained edges still contribute to the sum. ### What a Strong Answer Covers - Enforces the degree limit at every endpoint while maximizing the total across all remaining components. - Explains why no different set of removals can yield a larger sum. - Handles the full tree size, including a long path and a high-degree node. - Uses a return type suitable for the sum of many edge weights. ### Follow-up Questions - What should happen when every original degree is already at most `k`? - Why might keeping a positive-weight edge still reduce the best total achievable elsewhere? ```hint Distinguish the connection to a parent Root the tree temporarily. For each subtree, distinguish whether its root's edge to its parent is retained, since that changes how many child edges it may retain. ```