华为OD机试真题 新系统 2026-08-19 PythonJS【点亮战争迷雾】

目录

题目

思路

Code

题目

题目内容：

一张二叉树地图的所有节点都被战争迷雾覆盖。在某个节点放置侦察守卫，可以照亮该节点、父节点和直接子节点。节点 i 放置守卫的成本为 cost[i]。请选择若干节点放置守卫，使整棵树的每个节点都被照亮，并最小化总成本。

输入描述：

本地命令行输入共四行。第一行是节点数 n；第二行是 left 数组，left[i] 为左孩子编号；第三行是 right 数组；第四行是 cost 数组。孩子编号为 -1 表示为空，输入保证构成一棵合法二叉树。

输出描述：

输出照亮整棵树所需的最小总成本。

样例 1

输入：

3 1 -1 -1 2 -1 -1 5 1 1

输出：

2

说明：

在两个叶子节点放置守卫总成本为 2，可以同时照亮根节点和全部叶子。

思路

整体思路：每个节点是否被照亮取决于自己、父亲和孩子，使用后序树形动态规划维护三种状态。

第一步：状态分别表示当前节点放守卫、由孩子守卫照亮、暂未照亮并等待父节点守卫。

第二步：先递归计算孩子；当前放守卫时孩子三态都可选