트리 경로 분할
시간 제한1초메모리 제한128 MB
트리가 주어질 때 길이가 K 이하인 정점 분리 경로들로 모든 도시를 덮는 데 필요한 최소 경로 수를 구합니다.
문제
N개의 도시와 N - 1개의 도로가 주어진다. 도로망은 트리이므로 임의의 두 도시 사이에는 단순 경로가 정확히 하나 존재한다.
두 도시 u와 v 사이의 경로는 인접한 도로를 따라 u에서 v로 이동할 때 지나는 도시들의 순서이며, 같은 도시를 두 번 지나서는 안 된다. 경로의 길이는 그 경로에 포함된 도로의 개수이다.
양의 정수 K에 대해, 트리의 K-경로 분할은 다음 조건을 모두 만족하는 경로들의 집합이다.
- 서로 다른 두 경로는 같은 도시를 공유하지 않는다.
- 모든 도시는 정확히 하나의 경로에 포함된다.
- 각 경로의 길이는 K 이하이다.
도로망과 K가 주어질 때, 가능한 K-경로 분할 중 경로 수의 최솟값을 구하라.
입력
첫째 줄에 두 정수 N과 K가 주어진다. N은 도시의 수이며 2 <= N <= 300000을 만족한다. K는 1 <= K <= N - 1을 만족하는 정수이다.
다음 N - 1개의 줄에는 각 도로의 양 끝 도시를 나타내는 두 정수가 주어진다.
출력
K-경로 분할에서 가능한 경로 수의 최솟값을 출력한다.