当前位置: 首页 > news >正文

树形Dp 2925. 在树上执行操作以后得到的最大分数

2925. 在树上执行操作以后得到的最大分数
两次DFS

class Solution {
public:// 节点状态有两种,选和不选,// dp(u, fa, 0) 不选u 节点,其他节点都可以选,值为以u为根的子树的所有节点的和- 根节点的值。// dp(u, fa, 1) 选u节点, 其他子几点不选。vector<vector<int>> g;int n;vector<long long> gsum;void dfs(int u, int fa, vector<int>& values) {for (auto v : g[u]) {if (v == fa) continue;dfs(v, u, values);gsum[u] += gsum[v];}gsum[u] += values[u];return;}vector<long long> dp0;vector<long long> dp1;void Dfs2(int u, int fa, vector<int>& values) {dp1[u] += values[u];for (auto v : g[u]) {if (v == fa) continue;Dfs2(v, u, values);if (g[v].size() == 1) { // 叶子节点dp1[u] += dp0[v];} else {dp1[u] += max(dp1[v], dp0[v]);}}}long long maximumScoreAfterOperations(vector<vector<int>>& edges, vector<int>& values) {n = edges.size() + 1;g.resize(n);for (auto edge : edges) {g[edge[0]].push_back(edge[1]);g[edge[1]].push_back(edge[0]);}gsum.resize(n, 0);dfs(0, -1, values);cout << endl;dp0.resize(n);for(int i = 0; i < n; i++) {dp0[i] = gsum[i] - values[i];}dp1.resize(n);Dfs2(0, -1, values);return max(dp0[0], dp1[0]);}
};

一次dfs

class Solution {
public:// 节点状态有两种,选和不选,// dp(u, fa, 0) 不选u 节点,其他节点都可以选,值为以u为根的子树的所有节点的和- 根节点的值。// dp(u, fa, 1) 选u节点, 其他子几点不选。vector<vector<int>> g;int n;vector<long long> dp0;vector<long long> dp1;void Dfs2(int u, int fa, vector<int>& values) {dp1[u] += values[u];for (auto v : g[u]) {if (v == fa) continue;Dfs2(v, u, values);dp0[u] += dp0[v] + values[v];if (g[v].size() == 1) { // 叶子节点, 注意叶子节点的size 为1,不是0dp1[u] += dp0[v];} else {dp1[u] += max(dp1[v], dp0[v]);}}}long long maximumScoreAfterOperations(vector<vector<int>>& edges, vector<int>& values) {n = edges.size() + 1;g.resize(n);for (auto edge : edges) {g[edge[0]].push_back(edge[1]);g[edge[1]].push_back(edge[0]);}dp0.resize(n);dp1.resize(n);Dfs2(0, -1, values);return max(dp0[0], dp1[0]);}
};

相关文章:

树形Dp 2925. 在树上执行操作以后得到的最大分数

2925. 在树上执行操作以后得到的最大分数 两次DFS class Solution { public:// 节点状态有两种&#xff0c;选和不选&#xff0c;// dp(u, fa, 0) 不选u 节点&#xff0c;其他节点都可以选&#xff0c;值为以u为根的子树的所有节点的和- 根节点的值。// dp(u, fa, 1) 选u节点&…...

选择企业云盘?品牌推荐和评价解析

企业云盘是如今热门的企业协作工具&#xff0c;为企业提供了文件存储、文件共享服务。市面上的企业云盘千千万&#xff0c;到底哪个企业云盘好用&#xff1f;哪些品牌值得信赖呢&#xff1f; 好用的企业云盘&#xff0c;不能不提&#xff0c;Zoho Workdrive企业云盘为企业提供…...

redis: 记录一次线上redis内存占用过大问题解决过程

引言 记录一次线上redis占用过大的排查过程&#xff0c;供后续参考 问题背景 测试同事突然反馈测试环境的web系统无法登陆&#xff0c;同时发现其他子系统也存在各类使用问题 排查过程 1、因为首先反馈的是测试环境系统无法登陆&#xff0c;于是首先去查看了登陆功能的报错…...

数据资产、数字资产、数据资源及数据资产入表

数据要素 《中共中央关于坚持和完善中国特色社会主义制度推进国家治理体系和治理能力现代化若干重大的决议》&#xff08;2019&#xff09; 首次将数据列为生产要素 《关于构建更加完善的要素市场化配置体制机制的意见》&#xff08;2020.3&#xff09; 数据成为土地、劳动力、…...

Docker之Centos安装

介绍 Docker官方建议在Ubuntu中安装&#xff0c;因为Docker是基于Ubuntu发布的&#xff0c; 而且一般Docker出现的问题Ubuntu是最先更新或者打补丁的。 在很多版本的CentOS中是不支持更新最新的一些补丁包的。由于我们学习的环境都使用的是CentOS&#xff0c;因此这里我们将Do…...

SQL注入漏洞:CMS布尔盲注python脚本编写

SQL注入漏洞:CMS布尔盲注python脚本编写 文章目录 SQL注入漏洞:CMS布尔盲注python脚本编写库名爆破爆破表名用户名密码爆破 库名爆破 import requests #库名 database"" x0 while requests.get(urlf"http://10.9.47.77/cms/show.php?id33%20and%20length(data…...

security

Java Security 是一个用于在 Java 平台上提供安全性的框架。下面是 Java Security 的一些主要知识点&#xff1a; 1. 加密和解密&#xff1a;Java Security 提供了一组加密和解密 API&#xff0c;可以实现各种加密标准&#xff0c;如 AES、DES、RSA 等。 2. 数字签名&#xf…...

了解web3,什么是web3

Web3是指下一代互联网&#xff0c;它基于区块链技术&#xff0c;将各种在线活动更加安全、透明和去中心化。Web3是一个广义的概念&#xff0c;它包括了很多方面&#xff0c;如数字货币、去中心化应用、智能合约等等。听不懂且大多数人听到这个东西&#xff0c;直觉感觉就像骗子…...

Harbor企业级Registry基础镜像仓库的详细安装使用教程(保姆级)

Harbor Docker 官方提供的私有仓库 registry&#xff0c;用起来虽然简单 &#xff0c;但在管理的功能上存在不足。 Harbor是vmware一个用于存储和分发Docker镜像的企业级Registry服务器&#xff0c;harbor使用的是官方的docker registry(v2命名是distribution)服务去完成。 ha…...

Linux系统下数据同步服务RSYNC

一、RSYNC概述 1、什么是rsync rsync的好姐妹 sync 同步&#xff1a;刷新文件系统缓存&#xff0c;强制将修改过的数据块写入磁盘&#xff0c;并且更新超级块。 async 异步&#xff1a;将数据先放到缓冲区&#xff0c;再周期性&#xff08;一般是30s&#xff09;的去同步到磁…...

Docker介绍及其常用命令

Docker是一种容器化技术&#xff0c;可以打包应用程序及其依赖项&#xff0c;并将其作为独立的进程运行。它实现了操作系统级别的虚拟化&#xff0c;允许不同容器之间相互隔离&#xff0c;同时提高了应用程序的可移植性和安全性。Docker可以快速部署和扩展应用程序&#xff0c;…...

SwissArmyTransformer瑞士军刀工具箱使用手册

Introduction sat&#xff08;SwissArmyTransformer&#xff09;是一个灵活而强大的库&#xff0c;用于开发您自己的Transformer变体。 sat是以“瑞士军刀”命名的&#xff0c;这意味着所有型号&#xff08;例如BERT、GPT、T5、GLM、CogView、ViT…&#xff09;共享相同的backo…...

unity【动画】脚本_角色动画控制器 c#

首先创建一个代码文件夹Scripts 从人物角色Player的基类开始 创建IPlayer类 首先我们考虑到如果不挂载MonoBehaviour需要将角色设置成预制体实例化到场景上十分麻烦&#xff0c; 所以我们采用继承MonoBehaviour类的角色基类方法写代码 也就是说这个脚本直接绑定在角色物体…...

Java代码如何对Excel文件进行zip压缩

1&#xff1a;新建 ZipUtils 工具类 package com.ly.cloud.datacollection.util;import java.io.File; import java.io.FileInputStream; import java.io.FileOutputStream; import java.io.IOException; import java.io.OutputStream; import java.net.URLEncoder; import ja…...

改进YOLO系列:12.Repulsion损失函数【遮挡】

1. RepLoss论文 物体遮挡问题可以分为类内遮挡和类间遮挡两种情况。类间遮挡产生于扎堆的同类物体,也被称为密集遮挡(crowd occlusion)。Repulsion损失函数由三个部分构成,yolov5样本匹配,得到的目标框和预测框-一对应第一部分主要作用:预测目标框吸引IOU最大的真实目标框,…...

win11网络连接正常,但是无法正常上网

前言&#xff1a; 这个是一个win11的bug&#xff0c;好多人都遇到了&#xff0c;在孜孜不倦的百度下&#xff0c;毫无收获&#xff0c;终于是在抖音上看到有人分享的经验而解决了这个问题。 找到internet选项&#xff0c;然后点击打开 选择连接 将代理服务器中&#xff0c;为…...

硬科技企业社区“曲率引擎”品牌正式发布

“曲率引擎”&#xff0c;是科幻作品中最硬核的加速系统&#xff0c;通过改变时空的曲率&#xff0c;可实现光速飞行甚至能够超越光速。11月3日&#xff0c;“曲率引擎&#xff08;warp drive&#xff09;”作为硬科技企业社区品牌&#xff0c;在2023全球硬科技创新大会上正式对…...

少儿编程 2023年9月中国电子学会图形化编程等级考试Scratch编程三级真题解析(判断题)

2023年9月scratch编程等级考试三级真题 判断题(共10题,每题2分,共20分) 19、运行程序后,“我的变量”的值为25 答案:对 考点分析:考查积木综合使用,重点考查变量和运算积木的使用 开始我的变量为50,执行完第二行代码我的变量变为49,条件不成立执行否则语句,所以…...

MCU常见通信总线串讲(二)—— RS232和RS485

&#x1f64c;秋名山码民的主页 &#x1f602;oi退役选手&#xff0c;Java、大数据、单片机、IoT均有所涉猎&#xff0c;热爱技术&#xff0c;技术无罪 &#x1f389;欢迎关注&#x1f50e;点赞&#x1f44d;收藏⭐️留言&#x1f4dd; 获取源码&#xff0c;添加WX 目录 前言一…...

LazyVim: 将 Neovim 升级为完整 IDE | 开源日报 No.67

curl/curl Stars: 31.5k License: NOASSERTION Curl 是一个命令行工具&#xff0c;用于通过 URL 语法传输数据。 核心优势和关键特点包括&#xff1a; 可在命令行中方便地进行数据传输支持多种协议 (HTTP、FTP 等)提供丰富的选项和参数来满足不同需求 kubernetes/ingress-n…...

浅谈 React Hooks

React Hooks 是 React 16.8 引入的一组 API&#xff0c;用于在函数组件中使用 state 和其他 React 特性&#xff08;例如生命周期方法、context 等&#xff09;。Hooks 通过简洁的函数接口&#xff0c;解决了状态与 UI 的高度解耦&#xff0c;通过函数式编程范式实现更灵活 Rea…...

【HarmonyOS 5.0】DevEco Testing:鸿蒙应用质量保障的终极武器

——全方位测试解决方案与代码实战 一、工具定位与核心能力 DevEco Testing是HarmonyOS官方推出的​​一体化测试平台​​&#xff0c;覆盖应用全生命周期测试需求&#xff0c;主要提供五大核心能力&#xff1a; ​​测试类型​​​​检测目标​​​​关键指标​​功能体验基…...

linux 错误码总结

1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...

TRS收益互换:跨境资本流动的金融创新工具与系统化解决方案

一、TRS收益互换的本质与业务逻辑 &#xff08;一&#xff09;概念解析 TRS&#xff08;Total Return Swap&#xff09;收益互换是一种金融衍生工具&#xff0c;指交易双方约定在未来一定期限内&#xff0c;基于特定资产或指数的表现进行现金流交换的协议。其核心特征包括&am…...

《基于Apache Flink的流处理》笔记

思维导图 1-3 章 4-7章 8-11 章 参考资料 源码&#xff1a; https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...

【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)

升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点&#xff0c;但无自动故障转移能力&#xff0c;Master宕机后需人工切换&#xff0c;期间消息可能无法读取。Slave仅存储数据&#xff0c;无法主动升级为Master响应请求&#xff…...

(转)什么是DockerCompose?它有什么作用?

一、什么是DockerCompose? DockerCompose可以基于Compose文件帮我们快速的部署分布式应用&#xff0c;而无需手动一个个创建和运行容器。 Compose文件是一个文本文件&#xff0c;通过指令定义集群中的每个容器如何运行。 DockerCompose就是把DockerFile转换成指令去运行。 …...

Mac下Android Studio扫描根目录卡死问题记录

环境信息 操作系统: macOS 15.5 (Apple M2芯片)Android Studio版本: Meerkat Feature Drop | 2024.3.2 Patch 1 (Build #AI-243.26053.27.2432.13536105, 2025年5月22日构建) 问题现象 在项目开发过程中&#xff0c;提示一个依赖外部头文件的cpp源文件需要同步&#xff0c;点…...

零基础在实践中学习网络安全-皮卡丘靶场(第九期-Unsafe Fileupload模块)(yakit方式)

本期内容并不是很难&#xff0c;相信大家会学的很愉快&#xff0c;当然对于有后端基础的朋友来说&#xff0c;本期内容更加容易了解&#xff0c;当然没有基础的也别担心&#xff0c;本期内容会详细解释有关内容 本期用到的软件&#xff1a;yakit&#xff08;因为经过之前好多期…...

10-Oracle 23 ai Vector Search 概述和参数

一、Oracle AI Vector Search 概述 企业和个人都在尝试各种AI&#xff0c;使用客户端或是内部自己搭建集成大模型的终端&#xff0c;加速与大型语言模型&#xff08;LLM&#xff09;的结合&#xff0c;同时使用检索增强生成&#xff08;Retrieval Augmented Generation &#…...