도로 건설
면접 대비시간 제한2초메모리 제한512 MB
가중치가 있는 트리에서 각 간선이 트리를 나누는 두 부분의 크기 차이의 절댓값에 간선 길이를 곱한 값을 모두 더해 출력한다.
문제
행성 W에는 n개의 나라가 있다. 각 나라의 경제 성장을 도모하기 위해, 나라들의 왕은 모든 나라가 연결되도록 양방향 도로를 건설하기로 했다. 그러나 왕들은 모두 지독하게 인색해서, 정확히 n − 1개의 도로만 건설하려 한다.
각 도로를 건설하려면 비용이 든다. 이 비용은 도로의 길이에 도로 양쪽에 있는 나라 수의 차의 절댓값을 곱한 값과 같다. 예를 들어 아래 그림에서 점선으로 표시된 도로는 양쪽에 각각 2개와 4개의 나라가 있다. 이 도로의 길이가 1이라면 비용은 1×|2 − 4| = 2이다. 동그라미로 표시된 수는 나라의 번호이다.
나라의 수와 도로를 건설하는 방법의 수가 모두 매우 많고, 각 방법의 건설 비용도 사람이 계산하기 어려워서, 왕들은 소프트웨어를 설계할 사람을 고용하기로 했다. 이 소프트웨어는 도로를 건설하는 방법이 주어졌을 때 모든 도로를 건설하는 총비용을 계산할 수 있어야 한다. 왕들을 도와 그러한 프로그램을 작성하자.
입력
첫째 줄에는 행성 W에 있는 나라 수를 나타내는 정수 n이 주어진다. 나라는 1번부터 n번까지 번호가 매겨져 있다.
다음 n − 1개 줄에는 각각 하나의 도로 건설을 설명한다. 이 줄 중 i번째 줄에는 세 정수 ai, bi, ci가 주어지는데, i번째 양방향 도로가 나라 ai와 bi를 연결하고 길이가 ci라는 뜻이다.
출력
모든 도로를 건설하는 총비용을 정수 하나로 출력한다.
제한
- 1 ≤
ai,bi≤n - 2 ≤ n ≤ 106
- 0 ≤
ci≤ 106