60035 주유소 Platinum III

문제

KOI 국가는 $N$개의 마을로 이루어져 있다. 각 마을에는 $1$번 마을, $2$번 마을, $\cdots$, $N$번 마을과 같이 번호가 붙어 있다. 그리고 도로가 $N - 1$개 있는데, 각각의 도로는 서로 다른 두 마을을 잇고 있다. 각 도로에도 $1$번 도로, $2$번 도로, $\cdots$, $N - 1$번 도로와 같이 번호가 붙어 있다. $i$번 도로는 $x_i$번 마을과 $y_i$번 마을을 직접 잇고 있다. KOI 국가의 임의의 두 마을에 대해, 두 마을을 잇는 경로가 정확히 하나 존재한다.

$x$번 마을과 $y$번 마을을 잇는 경로는 $x$번 마을 - $z_1$번 마을 - $z_2$번 마을 - $\cdots$ - $z_t$번 마을 - $y$번 마을과 같이 마을로 이루어진 수열 형태를 띤다. 이 수열이 다음 두 성질을 만족할 때 경로라고 부른다.

• 경로를 이루는 인접한 두 마을 사이, 즉 $x$번 마을과 $z_1$번 마을 사이, $z_1$번 마을과 $z_2$번 마을 사이, $\cdots$, $z_t$번 마을과 $y$번 마을 사이를 잇는 도로가 존재한다.
• 경로에는 같은 마을이 두 번 등장하면 안 된다. 즉, 경로를 이루는 $x$번, $z_1$, $\cdots$, $z_t$번, $y$번 마을은 모두 서로 다른 마을이어야 한다.

이 때 경로의 “길이”는, 경로를 이루는 도로의 수, 즉 $t + 1$로 정의한다.

마을들 중 몇 개의 마을을 골라 주유소를 설치하려 한다. KOI 국가의 법에 따라, 주유소는 다음 조건을 만족하도록 설치해야 한다.

• 길이 $k$인 임의의 경로에, 주유소가 설치된 마을이 적어도 하나 존재해야 한다.

위 조건을 만족하도록 가장 적은 개수의 마을을 골라 주유소를 설치하려 한다. 이 때 설치해야 하는 주유소의 개수의 최솟값을 구하여라.

입력

첫 번째 줄에, 마을의 개수 $N$과 조건에 주어진 값 $k$가 공백을 사이에 두고 주어진다.

두 번째 줄부터 $N - 1$개의 줄에 걸쳐, 각 도로가 잇고 있는 두 마을의 번호 $x_i$와 $y_i$가 공백을 사이에 두고 주어진다.

출력

첫 번째 줄에, 설치해야 하는 주유소의 개수의 최솟값을 출력하라.

제한

• $2 ≤ N ≤ 200\,000$
• $1 ≤ k ≤ N - 1$
• $1 ≤ x_i ≤ N$, $1 ≤ y_i ≤ N$, $x_i \ne y_i$ ($1 ≤ i ≤ N - 1$)
• 임의의 두 마을에 대해, 두 마을을 잇는 경로가 정확히 하나 존재한다.
• 길이 $k$인 경로는 적어도 하나 존재한다.
• 주어지는 모든 수는 정수이다.

서브태스크

번호	배점	제한
1	9	$i$ ($1 ≤ i ≤ N - 1$)번 도로는 $i$번 마을과 $i + 1$번 마을을 잇고 있다.
2	10	$k = 1$.
3	11	$i$ ($1 ≤ i ≤ N - 1$)번 도로는 $i + 1$번 마을과 $\lfloor (i + 1)/2 \rfloor$번 마을을 잇고 있다. ($\lfloor x \rfloor$는 $x$ 이하인 가장 큰 정수를 의미한다)
4	12	$N ≤ 15$.
5	15	$N ≤ 300$.
6	17	$N ≤ 3\,000$.
7	26	추가 제약 조건 없음.

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

1

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

2