트리 색칠하기
시간 제한2초메모리 제한256 MB
트리가 주어질 때 인접한 정점끼리 다른 색을 갖도록 1부터 n까지의 색을 배정하여 색 번호 합의 최소값을 구하는 문제입니다.
문제
정점 n개로 이루어진 트리가 주어진다. 각 정점에는 1번부터 n번까지의 색 중 하나를 칠해야 한다. 색 i를 한 정점에 칠하는 비용은 i이다.
간선으로 직접 연결된 두 정점은 서로 다른 색이어야 한다. 이 조건을 만족하도록 모든 정점을 색칠할 때 드는 총비용의 최솟값을 구하라.
입력
첫째 줄에 정점의 개수이자 사용할 수 있는 색의 개수 n이 주어진다. (1 ≤ n ≤ 100,000)
다음 n - 1개의 줄에는 트리에서 간선으로 연결된 두 정점 u, v가 주어진다.
출력
모든 정점을 조건에 맞게 색칠하는 데 필요한 최소 총비용을 출력한다.