트리 분리하기

트리에서 두 정점 사이의 단순 경로에 놓인 정점을 모두 지운 뒤, 남은 그래프에서 크기가 K 이상인 연결 성분의 수를 최대로 만든다.

어려움8트리동적 계획법DFS그리디아직 제출이 없습니다시간 제한2초메모리 제한512 MB

문제 설명

예제6

문제

정점이 $N$ 개인 트리 $T$ 와 정수 $K$ 가 주어진다. $T$ 에서 서로 다른 두 정점 $u$ 와 $v$ 를 고르고, 두 정점을 잇는 단순 경로를 $P$ 라고 하자. $P$ 위의 정점을 모두 $T$ 에서 지우고, 양 끝점 가운데 하나 이상이 $P$ 위에 있는 간선도 함께 지운다.

남은 그래프에서 정점이 $K$ 개 이상인 연결 요소의 개수가 최대가 되도록 $u$ 와 $v$ 를 고르시오.

입력

입력은 다음 형식의 테스트 케이스 하나로 이루어진다.

N K
u1 v1
.
.
.
uN-1 vN-1

첫째 줄에 두 정수 $N$ , $K$ 가 주어진다 ( $2 \le N \le 100000$ , $1 \le K \le N$ ). 이어지는 $N-1$ 개의 줄은 간선 정보를 나타낸다. $i+1$ 번째 줄에는 두 정수 $u_i$ , $v_i$ 가 주어지며 ( $1 \le u_i, v_i \le N$ , $u_i \ne v_i$ ), $\{u_i, v_i\}$ 가 $T$ 의 간선임을 뜻한다. 주어지는 간선은 트리를 이룬다.

출력

정점이 $K$ 개 이상인 연결 요소의 최대 개수를 한 줄에 출력한다.