트리 분리하기

시간 제한2초메모리 제한512 MB

요약

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

난이도: 어려움10점 중 8점
유형: 트리, 동적 계획법, DFS, 그리디
정답자: 아직 제출이 없습니다

문제

정점이 $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$ 개 이상인 연결 요소의 최대 개수를 한 줄에 출력한다.

예제6

예제 1
입력
```
2 1
1 2
```
예상 출력
```
0
```
예제 2
입력
```
7 3
1 2
2 3
3 4
4 5
5 6
6 7
```
예상 출력
```
1
```

예제 3

입력

예상 출력

예제 4
입력
```
3 1
1 2
2 3
```
예상 출력
```
1
```
예제 5
입력
```
3 2
1 2
2 3
```
예상 출력
```
0
```
예제 6
입력
```
9 3
1 2
1 3
1 4
4 5
4 6
4 7
7 8
7 9
```
예상 출력
```
2
```