1693번 - 트리 색칠하기

문제

n개의 정점으로 이루어진 트리가 있다. 이 트리의 각 정점을 색칠하려고 한다. 색칠을 할 때에는 1, 2, 3, …, n번 색깔 중에 하나로 색칠하여야 한다. 각 색깔을 사용하여 한 개의 정점을 색칠할 때마다 1, 2, …, n의 비용이 든다. 즉, i번 색깔로 한 개의 정점을 색칠하면 i만큼의 비용이 든다는 것이다.

또한 정점에 색칠을 할 때에, 주어진 트리 상에서 인접해 있는 서로 다른 두 정점은 서로 다른 색깔로 칠해야 한다. 이를 만족하면서, 전체 정점을 색칠하는데 드는 총 비용을 최소화 하려 한다. 최소 비용을 계산하는 프로그램을 작성하시오.

입력

첫째 줄에는 정점 및 색깔의 개수 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 n-1개의 줄에는 각 줄에 두 개의 정수로 주어진 트리 상에서 연결되어 있는 두 정점의 번호가 주어진다.

출력

첫째 줄에 최소 비용을 출력한다.

제한

힌트