{"problem":{"name":"ρars/ey","description":{"content":"给定一颗有 $n$ 个节点的有根树，其中根节点是 $1$。你可以进行若干次以下操作: -   选择一个节点，删去其子树内除其以外的点。 此操作的代价为 $f_i$，其中 $i$ 是你选择的节点子树大小。 你希望删掉除了 $1$ 以外的所有点，请问代价的最小值是多少？ ","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8564"},"statements":[{"statement_type":"Markdown","content":"给定一颗有 $n$ 个节点的有根树，其中根节点是 $1$。你可以进行若干次以下操作:\n\n-   选择一个节点，删去其子树内除其以外的点。\n\n此操作的代价为 $f_i$，其中 $i$ 是你选择的节点子树大小。\n\n你希望删掉除了 $1$ 以外的所有点，请问代价的最小值是多少？\n\n## Input\n\n第一行一个正整数 $n$。\n\n第二行 $n-1$ 个正整数，第 $i$ 个表示 $f_{i+1}$。\n\n接下来 $n-1$ 行，每行两个正整数，表示一条树边。\n\n## Output\n\n一行一个正整数表示答案。\n\n[samples]\n\n## Note\n\n【样例解释】\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$ 之间连边。然后随机打乱所有节点的编号。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8564","tags":["洛谷原创","O2优化","背包 DP","树形 DP","洛谷月赛"],"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"]],"created_at":"2026-03-03 11:09:25"}}