Prune The Apple Tree

You are given a full binary tree representing an apple tree with (N) nodes numbered (1 \sim N), where node (1) is the root. Each edge (branch) connects two nodes and has a non‐negative integer number of apples on it. In this tree, if a node has any children then it has exactly two children (i.e. there is no node with only one child), except in the case where the tree has only one edge.

You need to prune the tree so that exactly (K) branches (edges) are kept. However, if an edge is kept, then the entire connected part from the root to that edge’s subtree remains intact. In other words, your selection of branches must form a connected subtree containing the root. Your task is to choose exactly (K) branches to maximize the total number of apples preserved on those branches.

The input is given as follows. The first line contains two integers (N) and (K). Each of the next (N-1) lines contains three integers (u), (v), and (a), denoting an edge connecting nodes (u) and (v) which bears (a) apples. It is guaranteed that the tree structure satisfies the full binary tree property and that node (1) is the root.

inputFormat

The first line contains two integers \(N\) and \(K\) (the number of nodes and the number of branches to keep). Each of the following \(N-1\) lines contains three integers \(u\), \(v\), and \(a\) where:

• \(u\) and \(v\) denote the endpoints of a branch (edge) in the tree.
• \(a\) denotes the number of apples on that branch.

It is guaranteed that the tree satisfies the full binary tree property with node \(1\) as the root.

outputFormat

Output a single integer, the maximum number of apples that can be preserved by keeping exactly \(K\) branches.

sample

1 0

0