好的，我将这道题整理为清晰的题面格式，并补充样例解释、数据范围与时空限制：

---

题目描述

有一棵二叉苹果树，如果数字有分叉，一定是分两叉，即没有只有一个儿子的节点（注：实际题目中的“二叉”指的是每个节点最多有两个子节点，但输入可能给出一般树，需要处理成二叉树）。这棵树共 $N$ 个节点，标号 $1$ 至 $N$，树根编号一定为 $1$。

我们用一根树枝两端连接的节点编号描述一根树枝的位置。一棵有四根树枝的苹果树，因为树枝太多了，需要剪枝。但是一些树枝上长有苹果，给定需要保留的树枝数量，求最多能留住多少苹果。

---

输入格式

第一行两个整数 $N$ 和 $Q$，$N$ 表示树的节点数，$Q$ 表示要保留的树枝数量。

接下来 $N-1$ 行，每行三个整数 $u, v, w$，表示树枝连接的两个节点编号以及这根树枝上的苹果数量。

---

输出格式

输出一行，一个整数，表示最多能留住的苹果的数量。

---

样例

样例输入

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

样例输出

21

样例解释

节点连接关系：

• 树枝 1-3，苹果数 1
• 树枝 1-4，苹果数 10
• 树枝 2-3，苹果数 20
• 树枝 3-5，苹果数 20

树形结构（以 1 为根）： 1 的子节点：3, 4
3 的子节点：2, 5

要保留 $Q=2$ 根树枝（注意保留的树枝数 = 保留的节点数 - 1，但这里说的是树枝数）。

保留树枝方案：保留 1-4（10 苹果）和 3-5（20 苹果）？这样总苹果 30，但需要验证是否可行。

实际上保留两根树枝意味着保留 3 个节点。
一种可行方案：保留节点 1, 3, 5，对应的树枝是 1-3（1 苹果）和 3-5（20 苹果），总苹果 21。

另一种方案：保留 1, 3, 4，树枝 1-3（1 苹果）和 1-4（10 苹果）总苹果 11，不如 21 多。

保留 1, 4, 5 不可行，因为 1-4 和 1-5 没有直接树枝，5 必须通过 3 连接，所以必须保留 1-3 和 3-5。

因此最大苹果数为 21。

---

数据范围

对于 $100\%$ 的数据：

• $1 \le Q \le N \le 100$
• $N \neq 1$
• 每根树枝上苹果数量不超过 $30000$

---

时空限制

• 时间：$1000 \text{ ms}$
• 内存：$524288 \text{ KB}$

---

提示
此题为 树形 DP（树上背包） 问题。

将每条边的苹果数看作边权，要保留 $Q$ 条边，等价于保留 $Q+1$ 个节点（因为树有 $N$ 个节点时边数为 $N-1$）。

状态定义：$dp[u][k]$ 表示以 $u$ 为根的子树中保留 $k$ 条边（即 $k+1$ 个节点）时能获得的最大苹果数。

转移方程： 对于节点 $u$ 及其两个子节点 $v_1, v_2$（如果是二叉树，直接分左右；如果是一般树，可以转化为二叉树处理），枚举在左右子树中分别保留多少条边：

$$dp[u][j] = \max_{0 \le t \le j-1} \big\{ dp[v_1][t] + dp[v_2][j-1-t] + w(u,v_1) + w(u,v_2) \big\}$$

注意：要保留到子节点 $v$ 的边时，必须包含边 $(u,v)$，所以分配时需减去这条边。

实际代码中需要先建树，然后将多叉树转为二叉树（左孩子右兄弟），或者直接按一般树进行背包合并。

时间复杂度 $O(N \cdot Q^2)$，在 $N,Q \le 100$ 时可行。