Delete Edges into K Components - Mastercard Online Assessment

Problem Preview

"You are given an undirected weighted tree consisting of `N` vertices. You may delete any edges from the tree. After deleting edges, the tree must be divided into exactly `K` connected components. The cost of deleting an edge equals its weight. Find the minimum total cost of deleted edges. ### Input The first line contains two integers `N` and `K`. Each of the next `N−1` lines contains three integers ``` u v w ``` representing an edge of weight `w`. ### Output Print the minimum total deletion cost. ### Constraints * `2 ≤ N ≤ 2 × 10^5` * `1 ≤ K ≤ N` * `1 ≤ w ≤ 10^9` ### Example **Input** ``` 5 3 1 2 4 2 3 2 2 4 7 4 5 1 ``` **Output** ``` 3 ``` ### Explanation Delete edges of weights `2` and `1`. The tree becomes exactly three connected components. Total cost ``` 2 + 1 = 3 ``` ---"