문제가 더 이상 사업을 방해하는 내용이 아닙니다. 제목을 "도시 정비"로 수정해 주세요.

문제

알고리즘 나라는 N개의 도시로 구성되어 있다. 모든 도시들은 고속도로를 통해 직간접적으로 연결되어 있다. 고속도로는 N-1개만 존재한다.

알고리즘 나라는 도시를 하나 없애려고 한다. 이때 그 도시와 직접 연결된 고속도로도 함께 제거된다.

알고리즘 나라의 도시들은 가끔 정비가 필요하다. 정비에는 정비 기기가 필요하고, 도시마다 필요한 정비 기기의 최소 가격이 있다. 즉 한 도시에 필요한 정비 기기의 최소 가격이 x이면, 가격이 x 이상인 정비 기기를 사용해야 그 도시를 정비할 수 있다.

정비 기기는 고속도로를 통해서만 이동할 수 있다. 도시 정비는 긴급하지 않기 때문에, 고속도로로 연결된 도시들의 집합에는 한 대의 정비 기기만 사용된다.

당신은 정비 기기를 만드는 회사의 사장이다. 당신은 어떤 도시가 없어졌을 때 가장 매출이 높아지는지 분석하고 싶다. 매출은 알고리즘 나라의 모든 도시를 정비하는 데 필요한 최소 비용이다. 도시를 없앴을 때 가능한 가장 높은 매출을 출력하는 프로그램을 작성하여라.

입력

" 고속도로는 반드시 트리의 형태로 주어진다."를 지워 주세요. 문제 설명에 주어져 있습니다.