P12452 [INOI Team Selection 2021] Color Colony

当且仅当一条路径中所有边的颜色都不同时，这条路径是坏的；否则，这条路径是好的。 当且仅当树中存在一条长度为 $k$ 的坏路径时，这棵树是坏的；否则，这棵树是好的。 现在我们有一棵树，需要给它的边染色。染色方案的美观度定义为使用的不同颜色数量。我们希望在不使树变坏的前提下，最大化美观度。请问能达到的最大美观度是多少？

输入的第一行包含两个整数 $n$ 和 $k$，分别表示树的顶点数和禁止出现的坏路径长度。 接下来的 $n-1$ 行描述树的边。第 $i$ 行包含两个整数 $u$ 和 $v$，表示顶点 $u$ 和 $v$ 之间有一条边。保证这些边构成一棵树。

输出一个整数，表示可以使用的最大颜色数量。

### 数据范围 - $1 \leq k \leq n \leq 10^5$ - $1 \leq k \leq 30$ ### 子任务 | 子任务 | 分值 | 限制条件 | | :---: | :---: | :---: | | 1 | 19 | 树中每个顶点的度数不超过 3 | | 2 | 7 | $n \leq 10$ | | 3 | 18 | $n \leq 30$，$k \leq 10$ | | 4 | 22 | $n \leq 100$ | | 5 | 25 | $n \leq 50000$ | | 6 | 9 | 无额外限制 | 翻译由 DeepSeek V3 完成