二叉苹果树 题目描述 有一棵苹果树，如果树枝有分叉，一定是分二叉（就是说没有只有一个儿子的结点） 这棵树共有 N 个结点（叶子点或者树枝分叉点），编号为 1∼N，树根编号一定是 1。 我们用一根树枝

二叉苹果树

题目描述

efF100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
有一棵苹果树，如果树枝有分叉，一定是分二叉（就是说没有只有一个儿子的结点）efF100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
这棵树共有 N 个结点（叶子点或者树枝分叉点），编号为 1∼N，树根编号一定是 1。efF100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。下面是一颗有 4 个树枝的树：efF100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
2 5efF100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
\ /efF100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
 3   4efF100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
  \ /efF100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
   1efF100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
efF100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
efF100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
现在这颗树枝条太多了，需要剪枝。但是一些树枝上长有苹果。efF100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
给定需要保留的树枝数量，求出最多能留住多少苹果。

输入

efF100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
第一行 2 个整数 N 和 Q，分别表示表示树的结点数，和要保留的树枝数量。efF100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
接下来 N−1 行，每行 3 个整数，描述一根树枝的信息：efF100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
前 2 个数是它连接的结点的编号，第 3 个数是这根树枝上苹果的数量。

输出

efF100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
一个数，最多能留住的苹果的数量。

样例输入 

5 2
1 3 1
1 4 10
2 3 20
3 5 20

样例输出

21

提示

efF100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
1⩽Q<N⩽100，每根树枝上的苹果 ⩽3×10⁴。