The Older We Are, The Worse It Hurts

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

You traverse the whole tree starting at 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 starting vertex and the order of outgoing edges at each vertex arbitrarily. Write down the list of all vertices, (v1, v2, . . . , vn), sorted by the time you first arrive at them. You get a penalty of ∑i · avi.

Your goal is to minimize the penalty. Note that (v1, v2, . . . , vn) is a permutation of (1, 2, . . . , n), and v1 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 edge descriptions: the i-th of them contains two integers ui and vi (1 ≤ ui, vi ≤ n) denoting the edge between ui and vi. The next line contains n space-separated integers ai (1 ≤ ai ≤ 200 000).

The given edges form a tree.

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