18638번 - The Older We Are, The Worse It Hurts 다국어

문제

You are given a tree with n vertices. Each vertex i has a weight a_i.

You traverse the whole tree starting in an arbitrary vertex and moving along the edges so that each edge is traversed exactly once in each direction (in other words, you perform a depth-first search traversal choosing the initial vertex and the order of outgoing edges arbitrarily). Write down the list of all vertices, (v₁, v₂, . . . , v_n), sorted by the time when you first arrive at them. You get a penalty of ∑i · a_vi.

Your goal is to minimize the penalty. Note that (v₁, v₂, . . . , v_n) is a permutation of (1, 2, . . . , n), and v₁ is the vertex you start from.

입력

The first line contains the only integer n (1 ≤ n ≤ 200 000) denoting the number of vertices. The next n−1 lines contain edges descriptions: i-th of them contains two integers u_i and v_i (1 ≤ u_i, v_i ≤ n) denoting the edge between u_i and v_i. The third line contains n space-separated integers a_i (1 ≤ a_i ≤ 200 000).

It is guaranteed that the given edges represent a tree.

출력

Print a single line with a single integer on it: the minimum possible penalty.

제한

힌트