题目描述

$N$ 頂点の木があり、頂点には $1\ ～\ N$ の番号がついています。$N\ -\ 1$ 本の辺について、$i\ (1≦i≦N-1)$ 本目の辺は頂点 $A_i$ と頂点 $B_i$ を繋いでいます。

この木の直径を $K$ 以下にするために削除する必要のある頂点数の最小値を求めてください。 ただし、頂点を削除した後のグラフは連結になっていなければなりません。

木の直径とは、$2$ つの頂点間の距離の最大値のことを指します。$2$ つの頂点間の距離とは、$2$ つの頂点を結ぶパスに含まれる辺の本数を指します。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $K$ $A_1$ $B_1$ $A_2$ $B_2$ : $A_{N-1}$ $B_{N-1}$

输出格式

直径を $K$ 以下にするために削除する必要のある頂点数の最小値を出力せよ。

题目大意

题目描述

给你一棵 $N$ 个点的无向树，定义点 $u$ 和 $v$ 之间的距离是从 $u$ 到 $v$ 的简单路径上的边数。

你需要删除一些点，使树的直径小于等于 $K$，当且仅当删除某点不会对树的联通性产生影响时才可以删除。问至少删除多少点才可以满足要求。

数据范围

$2≤N≤2000$，$1≤K≤N-1$，保证给出的图是一棵树。

输入输出格式：

输入格式

第一行两个个整数 $N, K$。

之后 $N - 1$ 行描述一棵树。

输出格式

一个整数，表示最少删掉点的个数。

感谢 @ToBiChi 提供翻译

6 2
1 2
3 2
4 2
1 6
5 6

2

6 5
1 2
3 2
4 2
1 6
5 6

0

提示

制約

• $2≦N≦2000$
• $1≦K≦N-1$
• $1≦A_i≦N,\ 1≦B_i≦N$
• 与えられるグラフは木である。

Sample Explanation 1

木の構造は図のとおりです。 頂点 $5,6$ を削除すると直径を $2$ に出来ます。 

Sample Explanation 2

すでに直径が $K$ 以下なので、頂点を削除する必要はありません。