트리 분할

N개의 도시들과 이들 도시들을 연결하는 트리 형태의 도로망이 있다. 즉, 이 도로망은 임의의 두 도시 사이의 경로가 항상 하나만 있다. 다음은 11개의 도시들로 이루어진 트리 형태의 도로망의 예이다.

두 도시 u, v사이의 경로는 u로부터 인접한 도로들을 따라 v에 도달하는 길로서, 중간에 거치는 도시가 중복되어서는 안 된다. 이 경로는 u부터 시작하여 지나는 도시들을 순서대로 나열하여 나타낸다. 예를 들어, 9부터 10까지의 경로는 (9, 8, 2, 10)으로 나타낸다.

양의 정수 K에 대하여, 이 트리 형태의 도로망의 K-경로 분할은 다음 조건을 만족하는 경로들의 집합이다.

• 이들 경로들 중 임의의 두 경로가 같은 도시를 지나서는 안 된다,

• 도로망의 각 도시는 반드시 이들 경로 중 하나에 포함되어야 한다.

• 각 경로는 길이가 K 이하이어야 한다. 경로의 길이란, 이 경로 상에 있는 도로(간선)의 개수이다.

예를 들어, 위 그림에 있는 도로망의 2-경로 분할 중 하나는 다음과 같다.

{(1, 2, 10), (8, 9), (3, 4), (6, 5, 7), (11)}

이 2-경로 분할에 있는 경로들은 아래 그림에서 점선 부분으로 표시되어 있으며, 경로들의 개수가 5이다. 이는 경로들의 수가 최소인 2-경로 분할 중 하나이다.

또 다른 예로, 다음은 3-경로 분할 중 하나이다.

{(1, 2, 3, 4), (8, 9), (10), (6, 5, 11), (7)}

이 분할에서 경로 개수는 5로서 3-경로 분할 중 경로 수가 가장 작다.

또 다른 예로, 다음은 1-경로 분할 중 하나이다.

{(1, 2), (10), (8, 9), (3, 4), (5, 6), (11), (7)}

이 분할에서 경로 개수는 7로서 1-경로 분할 중 경로 수가 가장 작다.

트리 형태의 도로망과 K가 주어질 때, 경로 개수가 가장 작은 K-경로 분할의 경로 수를 구하는 프로그램을 작성하시오.

※ 이 문제의 채점 데이터는 공개된 공식 데이터가 없어 재구성한 것입니다. 문제 지문은 원본(정보올림피아드 기출)을 따릅니다.

첫째 줄에는 도시의 수 N과 K-경로 분할을 위한 수 K가 빈칸을 사이에 두고 입력된다. N은 2 이상 300,000이하이다. K는 1이상 N-1이하인 정수이다. 다음 N-1개의 각 줄에 도로의 양 끝 도시를 나타내는 두 정수가 빈칸을 사이에 두고 주어진다.

경로 개수가 가장 작은 K-경로 분할의 경로 수를 출력한다.

생성자가 기록되지 않았습니다.

출처 올림피아드 > 한국정보올림피아드 > KOI 2011 > 2차 대회 > 고등부 4번