题目内容

有一棵二叉树，每个节点上都住了一户居民。现在要给这棵树上的居民建设基站，每个基站只能覆盖她所在与相邻的节点，请问信号覆盖这棵树最少需要建设多少个基站

输入描述

题面描述

给定一棵 二叉树，树上每个节点代表一户居民。需要在若干节点上建设基站，每个基站可以覆盖其所在节点及与其相邻的左右子节点和父节点，覆盖距离为 $1$。求覆盖整棵树的最少基站数量。

思路

对每个节点 $u$，定义三种状态：

• $f[u][0]$：在节点 $u$ 放置基站，覆盖整棵子树所需的最少基站数。
• $f[u][1]$：不在节点 $u$ 放置基站，且节点 $u$ 已被覆盖（由子节点或父节 点的基站覆盖）。