首页 最新 热门 推荐

  • 首页
  • 最新
  • 热门
  • 推荐
2025年5月19日 星期一 9:31pm

C++深度优先搜索的应用:2925在树上执行操作以后得到的最大分数

  • 25-02-22 04:41
  • 3437
  • 12571
blog.csdn.net

涉及知识点

深度优先搜索(DFS)

LeetCode2925在树上执行操作以后得到的最大分数

有一棵 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& 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 m_vNeiB;
};

class Solution {
public:
long long maximumScoreAfterOperations(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& 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& 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

文章知识点与官方知识档案匹配,可进一步学习相关知识
算法技能树首页概览60496 人正在系统学习中
群中有博文配套源码
QQ群名片
注:本文转载自blog.csdn.net的闻缺陷则喜何志丹的文章"https://blog.csdn.net/he_zhidan/article/details/134232424"。版权归原作者所有,此博客不拥有其著作权,亦不承担相应法律责任。如有侵权,请联系我们删除。
复制链接
复制链接
相关推荐
发表评论
登录后才能发表评论和回复 注册

/ 登录

评论记录:

未查询到任何数据!
回复评论:

分类栏目

后端 (14832) 前端 (14280) 移动开发 (3760) 编程语言 (3851) Java (3904) Python (3298) 人工智能 (10119) AIGC (2810) 大数据 (3499) 数据库 (3945) 数据结构与算法 (3757) 音视频 (2669) 云原生 (3145) 云平台 (2965) 前沿技术 (2993) 开源 (2160) 小程序 (2860) 运维 (2533) 服务器 (2698) 操作系统 (2325) 硬件开发 (2492) 嵌入式 (2955) 微软技术 (2769) 软件工程 (2056) 测试 (2865) 网络空间安全 (2948) 网络与通信 (2797) 用户体验设计 (2592) 学习和成长 (2593) 搜索 (2744) 开发工具 (7108) 游戏 (2829) HarmonyOS (2935) 区块链 (2782) 数学 (3112) 3C硬件 (2759) 资讯 (2909) Android (4709) iOS (1850) 代码人生 (3043) 阅读 (2841)

热门文章

101
推荐
关于我们 隐私政策 免责声明 联系我们
Copyright © 2020-2024 蚁人论坛 (iYenn.com) All Rights Reserved.
Scroll to Top