문제
노드가 N개 있고, 노드와 간선에 가중치가 부여된 트리가 있다. 경로의 가중치는 경로를 구성하는 간선 가중치의 총합에, 양쪽 끝 노드의 가중치의 곱을 더한 값이다. 경로의 길이가 0인 경우에는 가중치가 노드 가중치의 제곱으로 정의된다.
모든 노드에 대해, 그 노드에서 시작하는 경로들 중 가중치의 최솟값을 구하고, 앞에서 구한 값을 모두 더한 값을 출력하는 프로그램을 작성하여라.
입력
첫 번째 줄에는 노드의 수 N (1 ≤ N ≤ 200,000)가 주어진다.
두 번째 줄에는 정점의 가중치 Vi (1 ≤ Vi ≤ 106)가 N개 주어진다.
세 번째 줄부터 N-1개의 줄에는 트리의 각 간선이 연결하는 두 정점의 번호와, 그 간선의 가중치 w가 주어진다. (1 ≤ w ≤ 106)
출력
문제의 답을 출력한다.
예제
5
9 7 1 1 9
3 2 8
5 2 10
4 3 10
2 1 2
63
태그
출처
North American Invitational Programming Contest 2016
로그인해야 코드를 작성할 수 있어요.