3367. Maximize Sum of Weights after Edge Removals Hard

1/**
2 * [3367] Maximize Sum of Weights after Edge Removals
3 *
4 * 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.
5 * Your task is to remove zero or more edges such that:
6 * 
7 * 	Each node has an edge with at most k other nodes, where k is given.
8 * 	The sum of the weights of the remaining edges is maximized.
9 * 
10 * Return the maximum possible sum of weights for the remaining edges after making the necessary removals.
11 *  
12 * <strong class="example">Example 1:
13 * <div class="example-block">
14 * Input: <span class="example-io">edges = [[0,1,4],[0,2,2],[2,3,12],[2,4,6]], k = 2</span>
15 * Output: <span class="example-io">22</span>
16 * Explanation:
17 * <img alt="" src="https://assets.leetcode.com/uploads/2024/10/30/test1drawio.png" style="width: 250px; height: 250px;" />
18 * 
19 * 	Node 2 has edges with 3 other nodes. We remove the edge [0, 2, 2], ensuring that no node has edges with more than k = 2 nodes.
20 * 	The sum of weights is 22, and we can't achieve a greater sum. Thus, the answer is 22.
21 * </div>
22 * <strong class="example">Example 2:
23 * <div class="example-block">
24 * Input: <span class="example-io">edges = [[0,1,5],[1,2,10],[0,3,15],[3,4,20],[3,5,5],[0,6,10]], k = 3</span>
25 * Output: <span class="example-io">65</span>
26 * Explanation:
27 * 
28 * 	Since no node has edges connecting it to more than k = 3 nodes, we don't remove any edges.
29 * 	The sum of weights is 65. Thus, the answer is 65.
30 * </div>
31 *  
32 * Constraints:
33 * 
34 * 	2 <= n <= 10^5
35 * 	1 <= k <= n - 1
36 * 	edges.length == n - 1
37 * 	edges[i].length == 3
38 * 	<font face="monospace">0 <= edges[i][0] <= n - 1</font>
39 * 	<font face="monospace">0 <= edges[i][1] <= n - 1</font>
40 * 	<font face="monospace">1 <= edges[i][2] <= 10^6</font>
41 * 	The input is generated such that edges form a valid tree.
42 * 
43 */
44pub struct Solution {}
45
46// problem: https://leetcode.com/problems/maximize-sum-of-weights-after-edge-removals/
47// discuss: https://leetcode.com/problems/maximize-sum-of-weights-after-edge-removals/discuss/?currentPage=1&orderBy=most_votes&query=
48
49// submission codes start here
50
51impl Solution {
52    pub fn maximize_sum_of_weights(edges: Vec<Vec<i32>>, k: i32) -> i64 {
53        
54    }
55}
56
57// submission codes end
58
59#[cfg(test)]
60mod tests {
61    use super::*;
62
63    #[test]
64    fn test_3367() {
65    }
66}
67