{"raw_statement":[{"iden":"statement","content":"某城市的道路构成了一个巨大的树形结构，每一条道路可视为该结构的一条边，而道路的交叉点或端点视为其中的一个节点。该城市共有 $n$ 个节点，编号分别为 $1, 2, 3, \\ldots, n$。\n\n为了实时记录道路情况，需要在某些节点部署监控设备。当部署好后，与该节点直接相连的所有道路均能被监控到。为了优化资源分配，在保证整座城市的所有道路都被监控到的前提下，部署监控设备的费用要尽可能少。给定每个节点部署监控设备的费用，请计算要使所有道路都能被监控到的最少花费是多少？"},{"iden":"input","content":"- 第一行输入一个整数 $n$ ($2 \\leq n \\leq 10^4$)，表示城市中节点（即道路交叉点或端点）的数量；\n- 第二行输入 $n$ 个整数 ($1 <$ 整数 $\\leq 10^5$)，分别表示 $1$ 号到 $n$ 号节点部署监控设备的费用；\n- 接下来 $n-1$ 行，每行输入两个整数 $a$, $b$，表示节点 $a$ 和节点 $b$ 之间有一条道路。\n"},{"iden":"output","content":"输出一个整数，表示要使所有道路均能被监控到的最少花费。"}],"translated_statement":null,"sample_group":[["8\n33 12 30 22 18 10 31 28\n1 2\n1 3\n2 4\n2 5\n2 6\n3 7\n3 8","42"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}