{"raw_statement":[{"iden":"statement","content":"给定一颗有 $n$ 个节点的有根树，其中根节点是 $1$。你可以进行若干次以下操作:\n\n-   选择一个节点，删去其子树内除其以外的点。\n\n此操作的代价为 $f_i$，其中 $i$ 是你选择的节点子树大小。\n\n你希望删掉除了 $1$ 以外的所有点，请问代价的最小值是多少？\n\n\n\n\n\n"},{"iden":"input","content":"第一行一个正整数 $n$。\n\n第二行 $n-1$ 个正整数，第 $i$ 个表示 $f_{i+1}$。\n\n接下来 $n-1$ 行，每行两个正整数，表示一条树边。"},{"iden":"output","content":"一行一个正整数表示答案。"},{"iden":"note","content":"【样例解释】\n\n先删除节点 $8$ 的子树内除了它自身的 $5$ 个点，再删除节点 $1$ 的子树内除了它自身的 $2$ 个点，代价为 $f_6+f_3=63744$。可以证明这是最小的代价。\n\n【数据范围】\n\n对于所有数据，保证 $1\\le n\\le 5000$，$1\\le f_i\\le 10^9$。\n$$\n\\def\\arraystretch{1.5}\n\\begin{array}{c|c|c}\\hline \n\\textbf{测试点编号}&\\bm{~~~~~~~~n\\le~~~~~~~~}&~~~~\\textbf{特殊限制}~~~~\\cr\\hline \n\\textsf1\\sim \\sf2 & 8& \\cr\\hline \n\\sf3\\sim 6 & 15&  \\cr\\hline \n\\sf7\\sim 8 & 400&\\textsf{A}\\cr\\hline \n\\textsf9 & 400 &\\sf B\\cr\\hline \n\\sf10\\sim 12 & 400&\\cr\\hline\n\\sf13\\sim 14 & &\\sf C\\cr\\hline\n\\sf15\\sim 20 & &\\cr\\hline\n\\end{array}\n$$\n\n$\\textsf A$：保证树上所有点度数均小于等于 $2$，其中 $1$ 号点度数为 $1$。\n\n$\\textsf B$：保证树上只有 $1$ 号点度数大于等于 $2$。\n\n$\\textsf C$：保证树随机生成，随机生成方式是，对于 $i\\ge 2$，从 $[1,i-1]$ 中随机一个整数 $x$，在 $x$ 与 $i$ 之间连边。然后随机打乱所有节点的编号。"}],"translated_statement":null,"sample_group":[["8\n11000 18640 32793 36187 45104 64932 66425 \n6 8\n3 6\n3 7\n1 8\n1 4\n3 5\n2 7","63744"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}