나이가 들수록 더 아프다
시간 제한2초메모리 제한512 MB
트리의 루트를 임의로 정하고 각 정점의 자식 방문 순서를 조정해 DFS 발견 시각의 가중 합을 최소로 만들고, 그 최솟값을 출력한다.
문제
n개의 정점으로 이루어진 트리가 주어진다. 각 정점 i에는 가중치 ai가 있다.
임의의 정점에서 시작해 모든 간선을 각 방향으로 정확히 한 번씩 지나면서 트리 전체를 순회한다. 다시 말해, 시작 정점과 각 정점에서 나가는 간선의 순서를 임의로 정하는 깊이 우선 탐색을 수행한다. 이때 각 정점에 처음 도착한 시각 순으로 정점을 나열한 수열 (v1, v2, . . . , vn)을 적는다. 그러면 ∑i · avi의 벌점을 받는다.
벌점을 최소화하는 것이 목표이다. (v1, v2, . . . , vn)은 (1, 2, . . . , n)의 순열이고, v1은 시작 정점이다.
입력
첫째 줄에는 정점의 개수를 나타내는 정수 n (1 ≤ n ≤ 200 000)이 주어진다. 다음 n−1개 줄에는 간선의 정보가 주어진다. i번째 줄에는 ui와 vi (1 ≤ ui, vi ≤ n)가 주어지며, ui와 vi를 잇는 간선을 나타낸다. 그다음 줄에는 n개의 정수 ai (1 ≤ ai ≤ 200 000)가 공백으로 구분되어 주어진다.
주어진 간선들은 트리를 이룬다.
출력
가능한 벌점의 최솟값을 나타내는 정수 하나를 한 줄에 출력한다.