트리 경로 분할

N개의 도시와 N - 1개의 도로가 주어진다. 도로망은 트리이므로 임의의 두 도시 사이에는 단순 경로가 정확히 하나 존재한다.

두 도시 u와 v 사이의 경로는 인접한 도로를 따라 u에서 v로 이동할 때 지나는 도시들의 순서이며, 같은 도시를 두 번 지나서는 안 된다. 경로의 길이는 그 경로에 포함된 도로의 개수이다.

양의 정수 K에 대해, 트리의 K-경로 분할은 다음 조건을 모두 만족하는 경로들의 집합이다.

1. 서로 다른 두 경로는 같은 도시를 공유하지 않는다.
2. 모든 도시는 정확히 하나의 경로에 포함된다.
3. 각 경로의 길이는 K 이하이다.

도로망과 K가 주어질 때, 가능한 K-경로 분할 중 경로 수의 최솟값을 구하라.

첫째 줄에 두 정수 N과 K가 주어진다. N은 도시의 수이며 2 <= N <= 300000을 만족한다. K는 1 <= K <= N - 1을 만족하는 정수이다.

다음 N - 1개의 줄에는 각 도로의 양 끝 도시를 나타내는 두 정수가 주어진다.

K-경로 분할에서 가능한 경로 수의 최솟값을 출력한다.