[蓝桥杯青少年组国赛 2024] 第六题

Luogu

IDLGB4311

Time1000ms

Memory512MB

DifficultyP3

2024树形 DP蓝桥杯青少年组

某城市的道路构成了一个巨大的树形结构，每一条道路可视为该结构的一条边，而道路的交叉点或端点视为其中的一个节点。该城市共有 $n$ 个节点，编号分别为 $1, 2, 3, \ldots, n$。为了实时记录道路情况，需要在某些节点部署监控设备。当部署好后，与该节点直接相连的所有道路均能被监控到。为了优化资源分配，在保证整座城市的所有道路都被监控到的前提下，部署监控设备的费用要尽可能少。给定每个节点部署监控设备的费用，请计算要使所有道路都能被监控到的最少花费是多少？ ## Input - 第一行输入一个整数 $n$ ($2 \leq n \leq 10^4$)，表示城市中节点（即道路交叉点或端点）的数量； - 第二行输入 $n$ 个整数 ($1 <$ 整数 $\leq 10^5$)，分别表示 $1$ 号到 $n$ 号节点部署监控设备的费用； - 接下来 $n-1$ 行，每行输入两个整数 $a$, $b$，表示节点 $a$ 和节点 $b$ 之间有一条道路。 ## Output 输出一个整数，表示要使所有道路均能被监控到的最少花费。 [samples]

Samples

Input #1

8
33 12 30 22 18 10 31 28
1 2
1 3
2 4
2 5
2 6
3 7
3 8

Output #1

API Response (JSON)

{
  "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为了实时记录道路情况，需要在某些节点部署监控设备。当部署好后，与该节点直接相连的所有道路均能被监控到。为了优化资源分配，在保证整座城市的所有道路都被监控到的前提下，部署监控设备的费用要尽可能少。给定每个节...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments