트리 색칠하기

정점 n개로 이루어진 트리가 주어진다. 각 정점에는 1번부터 n번까지의 색 중 하나를 칠해야 한다. 색 i를 한 정점에 칠하는 비용은 i이다.

간선으로 직접 연결된 두 정점은 서로 다른 색이어야 한다. 이 조건을 만족하도록 모든 정점을 색칠할 때 드는 총비용의 최솟값을 구하라.

첫째 줄에 정점의 개수이자 사용할 수 있는 색의 개수 n이 주어진다. (1 ≤ n ≤ 100,000)

다음 n - 1개의 줄에는 트리에서 간선으로 연결된 두 정점 u, v가 주어진다.

모든 정점을 조건에 맞게 색칠하는 데 필요한 최소 총비용을 출력한다.