{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"Bob对树的数据结构非常感兴趣。树是一个有向图,其中有一个特殊的节点被称为树的“根”,并且从根到每个其他节点都有一条唯一的路径。\r\u003cbr\u003e\r\u003cbr\u003eBob打算用笔给树的所有节点上色。树有N个节点,这些节点编号为1, 2, ..., N。假设给一个节点上色需要1个单位的时间,完成一个节点的上色后,他可以继续上色另一个节点。此外,只有当父节点被上色后,他才能上色一个节点。显然,Bob只能在第一次尝试中给根节点上色。\r\u003cbr\u003e\r\u003cbr\u003e每个节点都有一个“上色成本因子”,Ci。每个节点的上色成本取决于Ci和Bob完成该节点上色的时间。在开始时,时间被设为0。如果节点i的上色完成时间为Fi,则节点i的上色成本为Ci * Fi。\r\u003cbr\u003e\r\u003cbr\u003e例如,图1显示了一个有五个节点的树。每个节点的上色成本因子分别为1, 2, 1, 2和4。Bob可以按照顺序给树上色为1, 3, 5, 2, 4,总上色成本最小为33。\r\u003cbr\u003e\u003ccenter\u003e\u003cimg src\u003d\"CDN_BASE_URL/e9ddd60daf5e3c2f5305b6db71c9d36b?v\u003d1703996170\"\u003e\u003c/center\u003e\r\u003cbr\u003e给定一棵树和每个节点的上色成本因子,请帮助Bob找到上色所有节点的最小可能总上色成本。"}},{"title":"输入","value":{"format":"HTML","content":"输入包含多个测试用例。每个用例的第一行包含两个整数N和R(1 ≤ N ≤ 1000, 1 ≤ R ≤ N),其中N是树中节点的数量,R是根节点的节点编号。第二行包含N个整数,第i个整数为Ci(1 ≤ Ci ≤ 500),表示节点i的上色成本因子。接下来的N-1行每行包含两个用空格分隔的节点编号V1和V2,它们是树中一条边的端点,表示V1是V2的父节点。不会重复列出边,且所有边都会被列出。\r\u003cbr\u003e\r\u003cbr\u003e当N \u003d 0且R \u003d 0时,表示输入结束,不应处理该行。"}},{"title":"输出","value":{"format":"HTML","content":"对于每个测试用例,输出一行,包含Bob上色所有节点所需的最小总上色成本。"}},{"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\u003e5 1\r\n1 2 1 2 4\r\n1 2\r\n1 3\r\n2 4\r\n3 5\r\n0 0\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e33\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}