{"problem":{"name":"[蓝桥杯青少年组国赛 2024] 第六题","description":{"content":"某城市的道路构成了一个巨大的树形结构，每一条道路可视为该结构的一条边，而道路的交叉点或端点视为其中的一个节点。该城市共有 $n$ 个节点，编号分别为 $1, 2, 3, \\ldots, n$。 为了实时记录道路情况，需要在某些节点部署监控设备。当部署好后，与该节点直接相连的所有道路均能被监控到。为了优化资源分配，在保证整座城市的所有道路都被监控到的前提下，部署监控设备的费用要尽可能少。给定每个节","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P3"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGB4311"},"statements":[{"statement_type":"Markdown","content":"某城市的道路构成了一个巨大的树形结构，每一条道路可视为该结构的一条边，而道路的交叉点或端点视为其中的一个节点。该城市共有 $n$ 个节点，编号分别为 $1, 2, 3, \\ldots, n$。\n\n为了实时记录道路情况，需要在某些节点部署监控设备。当部署好后，与该节点直接相连的所有道路均能被监控到。为了优化资源分配，在保证整座城市的所有道路都被监控到的前提下，部署监控设备的费用要尽可能少。给定每个节点部署监控设备的费用，请计算要使所有道路都能被监控到的最少花费是多少？\n\n## Input\n\n- 第一行输入一个整数 $n$ ($2 \\leq n \\leq 10^4$)，表示城市中节点（即道路交叉点或端点）的数量；\n- 第二行输入 $n$ 个整数 ($1 <$ 整数 $\\leq 10^5$)，分别表示 $1$ 号到 $n$ 号节点部署监控设备的费用；\n- 接下来 $n-1$ 行，每行输入两个整数 $a$, $b$，表示节点 $a$ 和节点 $b$ 之间有一条道路。\n\n## Output\n\n输出一个整数，表示要使所有道路均能被监控到的最少花费。\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"LGB4311","tags":["2024","树形 DP","蓝桥杯青少年组"],"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"]],"created_at":"2026-03-03 11:09:25"}}