涉及知识点
深度优先搜索(DFS)
题目
有一棵 n 个节点的无向树，节点编号为 0 到 n - 1 ，根节点编号为 0 。给你一个长度为 n - 1 的二维整数数组 edges 表示这棵树，其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 有一条边。
同时给你一个长度为 n 下标从 0 开始的整数数组 values ，其中 values[i] 表示第 i 个节点的值。
一开始你的分数为 0 ，每次操作中，你将执行：
选择节点 i 。
将 values[i] 加入你的分数。
将 values[i] 变为 0 。
如果从根节点出发，到任意叶子节点经过的路径上的节点值之和都不等于 0 ，那么我们称这棵树是 健康的 。
你可以对这棵树执行任意次操作，但要求执行完所有操作以后树是 健康的 ，请你返回你可以获得的 最大分数 。
示例 1：
输入：edges = [[0,1],[0,2],[0,3],[2,4],[4,5]], values = [5,2,5,2,1,1]
输出：11
解释：我们可以选择节点 1 ，2 ，3 ，4 和 5 。根节点的值是非 0 的。所以从根出发到任意叶子节点路径上节点值之和都不为 0 。所以树是健康的。你的得分之和为 values[1] + values[2] + values[3] + values[4] + values[5] = 11 。
11 是你对树执行任意次操作以后可以获得的最大得分之和。
示例 2：
输入：edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]], values = [20,10,9,7,4,3,5]
输出：40
解释：我们选择节点 0 ，2 ，3 和 4 。
- 从 0 到 4 的节点值之和为 10 。
- 从 0 到 3 的节点值之和为 10 。
- 从 0 到 5 的节点值之和为 3 。
- 从 0 到 6 的节点值之和为 5 。
所以树是健康的。你的得分之和为 values[0] + values[2] + values[3] + values[4] = 40 。
40 是你对树执行任意次操作以后可以获得的最大得分之和。
提示：
2 <= n <= 2 * 104
edges.length == n - 1
edges[i].length == 2
0 <= ai, bi < n
values.length == n
1 <= values[i] <= 109
输入保证 edges 构成一棵合法的树。
分析
时间复杂度
O(n)。两轮DFS，时间复杂度O(n)。每个节点处理的时间复杂度O(1)。 作为子树的根节点被处理一次，作为儿子节点处理一次。第一轮DFS 记录各节点及子孙节点所有价值。第二轮每个节点有两个选择：一，保留本节点，删除所有孙节点。二，删除本节点，各子节点必须保证各叶子节点健康。
注意：
一，叶子节点只能选择方式一。
二，不能用neiBo[cur]的元素数量判断是否是叶子节点，因为里面有父节点。
代码
核心代码
class CNeiBo2 { public: CNeiBo2(int n, bool bDirect, int iBase = 0):m_iN(n),m_bDirect(bDirect),m_iBase(iBase) { m_vNeiB.resize(n); } CNeiBo2(int n, vector<vector>& edges, bool bDirect,int iBase=0) :m_iN(n), m_bDirect(bDirect), m_iBase(iBase) { m_vNeiB.resize(n); for (const auto& v : edges) { m_vNeiB[v[0]- iBase].emplace_back(v[1]- iBase); if (!bDirect) { m_vNeiB[v[1]- iBase].emplace_back(v[0]- iBase); } } } inline void Add(int iNode1, int iNode2) { iNode1 -= m_iBase; iNode2 -= m_iBase; m_vNeiB[iNode1].emplace_back(iNode2); if (!m_bDirect) { m_vNeiB[iNode2].emplace_back(iNode1); } } const int m_iN; const bool m_bDirect; const int m_iBase; vector<vector> m_vNeiB; }; class Solution { public: long long maximumScoreAfterOperations(vector<vector>& edges, vector& values) { m_c = edges.size() + 1; m_values = values; m_vTotal.resize(m_c); m_vRet.resize(m_c); CNeiBo2 neiBo(m_c, edges, false); DFS(0, -1, neiBo.m_vNeiB); return DFS2(0, -1, neiBo.m_vNeiB); } void DFS(int cur, int parent, const vector<vector>& neiBo) { long long& curTotal = m_vTotal[cur]; curTotal = m_values[cur]; for (const auto& next : neiBo[cur]) { if (next == parent) { continue; } DFS(next, cur, neiBo); curTotal += m_vTotal[next]; } } long long DFS2(int cur, int parent, const vector<vector>& neiBo) { //保留本节点，其它权删除 long long curScore = m_vTotal[cur] - m_values[cur]; //删除本节点 long long curScore2 = m_values[cur]; bool bHasChild = false; for (const auto& next : neiBo[cur]) { if (next == parent) { continue; } curScore2 += DFS2(next, cur, neiBo); bHasChild = true; } if (!bHasChild) { curScore2 = 0; } return m_vRet[cur] = max(curScore, curScore2); } int m_c; vector m_vTotal; vector m_vRet; vector m_values; long long m_llRet = 0; };
测试用例
遗失。
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关下载
想高屋建瓴的学习算法，请下载《闻缺陷则喜算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
| 鄙人想对大家说的话 |
| 闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 墨家名称的来源：有所得以墨记之。 |
| 如果程序是一条龙，那算法就是他的是睛 |
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
