{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n div.illustration {\n float: right;\n padding-left: 20px;\n }\n div.illustration .illustration {\n width: 100%;\n border-radius: 4px;\n }\n pre {\n display: block;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n color: #333;\n word-break: break-all;\n word-wrap: break-word;\n }\n\u003c/style\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\[\u0027, right: \u0027\\\\]\u0027, display: true}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\n \u003cp\u003eThis is Yet Another Tree Problem. You are given a tree,\n where every node has a penalty and every edge has a weight. The\n cost of a simple path between any two nodes is the sum of the\n weights of the edges in the path, plus the product of the\n penalties of the endpoint nodes. Note that a path can have\n \u003cspan class\u003d\"tex2jax_process\"\u003e$0$\u003c/span\u003e edges, and the cost of\n such a path is simply the square of the penalty of the\n node.\u003c/p\u003e\n\n \u003cp\u003eFor each node, compute the smallest cost of any path\n starting at that node. The final answer is the sum of all of\n these minimum costs.\u003c/p\u003e\n\n \u003ch2\u003eInput\u003c/h2\u003e\n\n \u003cp\u003eEach input will consist of a single test case. Note that\n your program may be run multiple times on different inputs. The\n first line of input will consist of a single integer\n \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\le n \\le 200\\, 000$\u003c/span\u003e), which is the\n number of nodes. The next line will consist of \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e space-separated integers\n \u003cspan style\u003d\"width:\" class\u003d\"mbox\"\u003e\u003cspan class\u003d\"tex2jax_process\"\u003e$p$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$1\n \\le p \\le 1\\, 000\\, 000$\u003c/span\u003e)\u003c/span\u003e, which is the penalty\n of each node, in order. Each of the following \u003cspan class\u003d\"tex2jax_process\"\u003e$n-1$\u003c/span\u003e lines will consist of three\n space-separated integers \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003e, \u003cspan class\u003d\"tex2jax_process\"\u003e$j$\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$w$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$1\n \\le i \\le n, 1 \\le j \\le n, i \\ne j, 1 \\le w \\le 1\\, 000\\,\n 000$\u003c/span\u003e), specifying an edge between nodes \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$j$\u003c/span\u003e with weight \u003cspan class\u003d\"tex2jax_process\"\u003e$w$\u003c/span\u003e.\u003c/p\u003e\n\n \u003ch2\u003eOutput\u003c/h2\u003e\n\n \u003cp\u003eOutput a single integer, which is the sum of all of the\n lowest cost paths for each node.\u003c/p\u003e\n\n \u003ch2\u003eSample 1\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\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\u003e5\n9 7 1 1 9\n3 2 8\n5 2 10\n4 3 10\n2 1 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e63\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n "}}]}