{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e给定一个有 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e 个节点的树(从 \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e 到 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e 编号),以节点 \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e 为根。此外,每个节点都有两个与之相关联的值。第 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e 个节点的值为 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e 和 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eb\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e。\u003c/p\u003e\u003cp\u003e你可以从一个节点跳到其子树中的任何节点。从节点 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003c/span\u003e 跳到节点 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ey\u003c/i\u003e\u003c/span\u003e 的一次跳跃的成本是 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ex\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e 和 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eb\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ey\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e 的乘积。由一个或多个跳跃组成的路径的总成本是各个跳跃的成本之和。对于每个节点,计算到达该节点任意叶节点的最小总成本。请注意,即使根节点的度为 \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e,根节点也永远不可能是叶子节点。\u003c/p\u003e\u003cp\u003e请注意,你不能从一个节点跳到它自己。\u003c/p\u003e"}},{"title":"输入","value":{"format":"HTML","content":"\u003cp\u003e输入的第一行包含一个整数 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e(\u003cspan class\u003d\"tex-span\"\u003e2 ≤ \u003ci\u003en\u003c/i\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e5\u003c/sup\u003e\u003c/span\u003e)— 树中节点的数量。\u003c/p\u003e\u003cp\u003e第二行包含 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e 个空格分隔的整数 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e, \u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e, ..., \u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/sub\u003e( - 10\u003csup class\u003d\"upper-index\"\u003e5\u003c/sup\u003e ≤ \u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e5\u003c/sup\u003e)\u003c/span\u003e。\u003c/p\u003e\u003cp\u003e第三行包含 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e 个空格分隔的整数 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eb\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e, \u003ci\u003eb\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e, ..., \u003ci\u003eb\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/sub\u003e( - 10\u003csup class\u003d\"upper-index\"\u003e5\u003c/sup\u003e ≤ \u003ci\u003eb\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e5\u003c/sup\u003e)\u003c/span\u003e。\u003c/p\u003e\u003cp\u003e接下来的 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e - 1\u003c/span\u003e 行包含两个空格分隔的整数 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eu\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e 和 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ev\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e(\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003eu\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e, \u003ci\u003ev\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ \u003ci\u003en\u003c/i\u003e\u003c/span\u003e),描述树中节点 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eu\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e 和 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ev\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e 之间的边。\u003c/p\u003e"}},{"title":"输出","value":{"format":"HTML","content":"\u003cp\u003e输出 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e 个空格分隔的整数,其中第 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e 个表示从节点 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e 到达任意叶节点的最小成本。\u003c/p\u003e"}},{"title":"示例","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\u003e3\n2 10 -1\n7 -7 5\n2 3\n2 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e10 50 0 \u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"","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\n5 -10 5 7\n-8 -80 -3 -10\n2 1\n2 4\n1 3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e-300 100 0 0 \u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"注意","value":{"format":"HTML","content":"\u003cp\u003e在第一个示例中,节点 \u003cspan class\u003d\"tex-span\"\u003e3\u003c/span\u003e 已经是叶子节点,因此成本为 \u003cspan class\u003d\"tex-span\"\u003e0\u003c/span\u003e。对于节点 \u003cspan class\u003d\"tex-span\"\u003e2\u003c/span\u003e,跳到节点 \u003cspan class\u003d\"tex-span\"\u003e3\u003c/span\u003e 的成本为 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e × \u003ci\u003eb\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e3\u003c/sub\u003e \u003d 50\u003c/span\u003e。对于节点 \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e,直接跳到节点 \u003cspan class\u003d\"tex-span\"\u003e3\u003c/span\u003e 的成本为 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e × \u003ci\u003eb\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e3\u003c/sub\u003e \u003d 10\u003c/span\u003e。\u003c/p\u003e\u003cp\u003e在第二个示例中,节点 \u003cspan class\u003d\"tex-span\"\u003e3\u003c/span\u003e 和节点 \u003cspan class\u003d\"tex-span\"\u003e4\u003c/span\u003e 是叶子节点,因此成本为 \u003cspan class\u003d\"tex-span\"\u003e0\u003c/span\u003e。对于节点 \u003cspan class\u003d\"tex-span\"\u003e2\u003c/span\u003e,跳到节点 \u003cspan class\u003d\"tex-span\"\u003e4\u003c/span\u003e 的成本为 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e × \u003ci\u003eb\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e4\u003c/sub\u003e \u003d 100\u003c/span\u003e。对于节点 \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e,先跳到节点 \u003cspan class\u003d\"tex-span\"\u003e2\u003c/span\u003e 的成本为 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e × \u003ci\u003eb\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e \u003d - 400\u003c/span\u003e,然后从 \u003cspan class\u003d\"tex-span\"\u003e2\u003c/span\u003e 跳到 \u003cspan class\u003d\"tex-span\"\u003e4\u003c/span\u003e 的成本为 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e × \u003ci\u003eb\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e4\u003c/sub\u003e \u003d 100\u003c/span\u003e。\u003c/p\u003e"}}]}