{"raw_statement":[{"iden":"problem statement","content":"You are given a tree with $N$ vertices. The vertices are numbered $1$ to $N$, and the $i$\\-th edge connects vertices $A_i$ and $B_i$.\nYou are also given a sequence of positive integers $C = (C_1, C_2, \\ldots ,C_N)$ of length $N$. Let $d(a, b)$ be the number of edges between vertices $a$ and $b$, and for $x = 1, 2, \\ldots, N$, let $\\displaystyle f(x) = \\sum_{i=1}^{N} (C_i \\times d(x, i))$. Find $\\displaystyle \\min_{1 \\leq v \\leq N} f(v)$."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 10^5$\n*   $1 \\leq A_i, B_i \\leq N$\n*   The given graph is a tree.\n*   $1 \\leq C_i \\leq 10^9$"},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$\n$A_1$ $B_1$\n$A_2$ $B_2$\n$\\vdots$\n$A_{N - 1}$ $B_{N - 1}$\n$C_1$ $C_2$ $\\cdots$ $C_N$"},{"iden":"sample input 1","content":"4\n1 2\n1 3\n2 4\n1 1 1 2"},{"iden":"sample output 1","content":"5\n\nFor example, consider calculating $f(1)$. We have $d(1, 1) = 0, d(1, 2) = 1, d(1, 3) = 1, d(1, 4) = 2$.  \nThus, $f(1) = 0 \\times 1 + 1 \\times 1 + 1 \\times 1 + 2 \\times 2 = 6$.\nSimilarly, $f(2) = 5, f(3) = 9, f(4) = 6$. Since $f(2)$ is the minimum, print `5`."},{"iden":"sample input 2","content":"2\n2 1\n1 1000000000"},{"iden":"sample output 2","content":"1\n\n$f(2) = 1$, which is the minimum."},{"iden":"sample input 3","content":"7\n7 3\n2 5\n2 4\n3 1\n3 6\n2 1\n2 7 6 9 3 4 6"},{"iden":"sample output 3","content":"56"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}