{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003eThe members in *SOS Dan(**S**ekai o **O**oini Moriageru Tame no **S**uzumiya Haruhi no Dan)* want to assemble a Christmas tree(you know many Christmas trees are decorations not real trees).\u003cbr\u003e\u003cbr\u003eThe tree contains $n$ vertices which are numbered from $1$ to $n$. The weight of vertex $i$ is $w_i$. The number of edges on the path from vertex $i$ to vertex $1$(vertex $1$ is important because it\u0027s the top one) is denoted as $d_i$. \u003cbr\u003e\u003cbr\u003eHaruhi says, \"I don\u0027t like the vertex pairs $(i,j)$ that $i$ is the ancestor of $j$ and $w_i \u0026gt; w_j$ \".\u003cbr\u003e\u003cbr\u003eKyon says, \"I don\u0027t like the vertex pairs $(i,j)$ that $i$ is the ancestor of $j$ and $w_i \u0026lt; w_j$\".\u003cbr\u003e\u003cbr\u003eItsuki says, \"I don\u0027t like the vertex pairs $(i,j)$ that $i\u0026lt;j$ and neither $i$ nor $j$ is the ancestor of the other one\".\u003cbr\u003e\u003cbr\u003eMikuru says, \"I don\u0027t like the vertices that are far away from vertex $1$\".\u003cbr\u003e\u003cbr\u003eYuki says nothing.\u003cbr\u003e\u003cbr\u003eNow they are divided into two groups to assemble the tree. Haruhi and Itsuki are in group $A$ while Kyon and Mikuru are in group $B$. Both group choose some vertices to assemble. Each vertex should be chosen by exactly $1$ group.\u003cbr\u003e\u003cbr\u003eLet\u0027s denote the vertices set group $A$ chose as $V(A)$, the vertices set group $B$ chose as $V(B)$. The dislike level of group $A$ is $$|\\lbrace vertex \\; pair \\; (i,j) \\; that \\; is \\; disliked \\; by \\; either \\; Haruhi \\; or \\; Itsuku | i \\in V(A) \\bigwedge j \\in V(A) \\rbrace|$$. The dislike level of group $B$ is $$|\\lbrace vertex \\; pair \\; (i,j) \\; that \\; is \\; disliked \\; by \\; Kyon| i \\in V(B) \\bigwedge j \\in V(B) \\rbrace|+\\sum_{u \\in V(B)} d_u$$.\u003cbr\u003e\u003cbr\u003eYuki wants to know the minimum value of the sum of dislike level of group $A$ and $B$ when $|V(B)|\u003d1,2,3,\\cdots,n$ respectively.\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line contains an integer $n(1\\le n \\le 10^6)$ denoting the number of vertices on the tree.\u003cbr\u003e\u003cbr\u003eThe second line contains $n$ integer $w_i(1 \\le w_i \\le 10^6)$ denoting the weight of vertex $i$.\u003cbr\u003e\u003cbr\u003eNext $n-1$ lines each contains two integer $u,v(1\\le u,v \\le n)$, denoting there is an edge between $u$ and $v$.\u003cbr\u003e\u003cbr\u003e\u003cdiv style\u003d\"font-family:Times New Roman;font-size:14px;background-color:F4FBFF;border:#B7CBFF 1px dashed;padding:6px\"\u003e\u003cdiv style\u003d\"font-family:Arial;font-weight:bold;color:#7CA9ED;border-bottom:#B7CBFF 1px dashed\"\u003e\u003ci\u003eHint\u003c/i\u003e\u003c/div\u003e\u003cbr\u003e\u003cb\u003e样例解释\u003c/b\u003e\u003cbr\u003e\u003cbr\u003e$B\u003d\\emptyset,\\lbrace 3 \\rbrace, \\lbrace 3,4 \\rbrace, \\lbrace 1,3,4 \\rbrace,\\lbrace 1,2,3,4 \\rbrace$ respectively.\u003cbr\u003e\u003c/div\u003e"}},{"title":"Output","value":{"format":"HTML","content":"Output $n$ lines. The $i-th$ of them contains an integer denoting the answer when $|V(B)|\u003di$."}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4\r\n4 1 2 3\r\n1 2\r\n2 3\r\n2 4\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e9\r\n5\r\n2\r\n1\r\n2\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}