本题是华为秋招机考24年11月6日-第2题-铺设消防栓属于同一类题，可见树形dp的视频讲解

解题思路

给定用层序遍历（一维数组）表示的一棵二叉树，每个结点存放该结点灯泡的“亮度”。若选择打开某个结点的灯泡，则它的父结点和两个子结点的灯泡都不能打开。要求求出能获得的最大亮度总和。

这本质是树上最大权独立集问题。 对每个结点做树形 DP，设：

• dp1[i]：在以结点 i 为根的子树中，打开结点 i 的最大亮度和；
• dp0[i]：在以结点 i 为根的子树中，不打开结点 i 的最大亮度和。

题目内容

给定一个普通二叉树 bulbs , 我们在二叉树的节点上安装灯泡，每个灯泡都有自己的亮度值和开关，如果选择打开一个灯泡，则它相邻的父节点和子节点上的灯泡都不能被打开，计算能够获得的最大亮度总和。

输入描述

假设 $bulbs[$ $]$ 是使用层序遍历存储的二叉树，其元素数值代表该对应树节点上灯泡的亮度值。

第一行输入为一个整数 $n$ ，代表 $bulbs[$ $]$ 的数组大小;

第二行输入为 $n$ 个整数，代表 $bulbs[$ $]$ 的元素值。

关于层序遍历的说明：

简单来说就是从根节点开始，一层一层从上到下、从左到右逐层遍历二叉树的节点，并按顺序将遍历结果保存在一维数组中。这样，我们可以得到一个包含二叉树所有节点灯泡亮度值的一维数组，顺序就是层序遍历的顺序。如果某个位置没有节点，用 $0$ 来占位，代表该处没有节点，亮度是 $0$ 。

参数取值范围：

• $1 <= bulbs.length<=10^6$

• $0 <= bulbs[i]<= 100$

输出描述

一个整数，能够获得的最大亮度总和。

样例1

输入

5
1 2 3 0 4

输出

7

说明

样例2

输入

5
1 2 0 0 4

输出

5

说明