问题陈述
给你一棵树 $T$ 和一个整数 $K$。您可以在 $T$ 上选择任意不同的两个顶点 $u$ 和 $v$。令$P$ 为$u$ 和$v$ 之间的简单路径。然后,删除 $P$ 中的顶点和边,使其一个或两个末端顶点位于 $T$ 中的 $P$ 中。您的任务是选择 $u$ 和 $v$ 来最大化该操作后具有 $K$ 或更多 $T$ 顶点的连接组件的数量。
输入
输入由单个测试用例组成,格式如下。
$N\K$ $u_1\v_1$ $\vdots$ $u_{N-1} \ v_{N-1}$
第一行由两个整数$N, K \ (2 \le N \le 100{,}000, 1 \le K \le N)$组成。 接下来的$N-1$行代表边的信息。第 $(i+1)$ 行由两个整数 $u_i, v_i \ (1 \le u_i, v_i \le N \text{ 和 } u_i \ne v_i \text{ 对于每个 } i)$ 组成。每个$\{u_i, v_i\}$都是$T$的一条边。保证这些边形成一棵树。
输出
打印一行中具有 $K$ 或更多顶点的连通分量的最大数量。
示例输入 1
2 1 1 2
样本输入 1 的输出
0
示例输入 2
7 3 1 2 2 3 3 4 4 5 5 6 6 7
样本输入 2 的输出
1
示例输入 3
12 2 1 2 2 3 3 4 4 5 3 6 6 7 7 8 8 9 6 10 10 11 11 12
样本输入 3 的输出
4
示例输入 4
3 1 1 2 2 3
样本输入 4 的输出
1
示例输入 5
3 2 1 2 2 3
样本输入 5 的输出
0
示例输入 6
9 3 1 2 1 3 1 4 4 5 4 6 4 7 7 8 7 9
样本输入 6 的输出
2