← 返回题目列表

AtCoder · jag2017autumn_e

E. 树分离器

中文机器翻译题面 查看原题

问题陈述

给你一棵树 $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