개의 정점으로 이루어진 트리가 주어진다. 정점에는 번부터 번까지 번호가 붙어 있으며, 각 간선의 가중치는 또는 이다.
두 정점 사이의 트리 거리 는 두 정점을 잇는 유일한 경로에 포함된 간선들의 가중치 합으로 정의한다.
각 정점 를 수직선 위의 정수 좌표 에 배치하려고 한다. 서로 다른 모든 두 정점 에 대하여 다음 조건을 모두 만족해야 한다.
트리 거리가 인 두 정점도 서로 다른 좌표에 배치해야 한다.
배치의 길이 은 가장 오른쪽 정점과 가장 왼쪽 정점 사이의 거리이다.
조건을 만족하는 배치 중 의 최솟값을 구하여라.
입력은 다음과 같은 형식으로 주어진다.
각 테스트 케이스마다 조건을 만족하는 배치의 길이의 최솟값을 출력한다.
각 테스트 케이스는 다음과 같은 형식으로 주어진다.
번째 간선은 정점 와 를 잇고 가중치는 이다.
