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

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

양의 정수 K에 대하여, 이 트리 형태의 도로망의 K-경로 분할은 다음 조건을 만족하는 경로들의 집합이다. (1) 이들 경로들 중 임의의 두 경로가 같은 도시를 지나서는 안 된다, (2) 도로망의 각 도시는 반드시 이들 경로 중 하나에 포함되어야 한다. (3) 각 경로는 길이가 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-경로 분할의 경로 수를 구하는 프로그램을 작성하시오.

실행시간은 1초를 넘을 수 없다. 부분 점수는 없다.

#2505 upload 117회 done 34회 how_to_reg 22명

트리 분할 timer 1초 memory 256MB

#2505

트리 분할 1초 256MB