树形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:// 节点状态有两种,选和不选,// dp(u, fa, 0) 不选u 节点,其他节点都可以选,值为以u为根的子树的所有节点的和- 根节点的值。// dp(u, fa, 1) 选u节点&…...
选择企业云盘?品牌推荐和评价解析
企业云盘是如今热门的企业协作工具,为企业提供了文件存储、文件共享服务。市面上的企业云盘千千万,到底哪个企业云盘好用?哪些品牌值得信赖呢? 好用的企业云盘,不能不提,Zoho Workdrive企业云盘为企业提供…...
redis: 记录一次线上redis内存占用过大问题解决过程
引言 记录一次线上redis占用过大的排查过程,供后续参考 问题背景 测试同事突然反馈测试环境的web系统无法登陆,同时发现其他子系统也存在各类使用问题 排查过程 1、因为首先反馈的是测试环境系统无法登陆,于是首先去查看了登陆功能的报错…...
数据资产、数字资产、数据资源及数据资产入表
数据要素 《中共中央关于坚持和完善中国特色社会主义制度推进国家治理体系和治理能力现代化若干重大的决议》(2019) 首次将数据列为生产要素 《关于构建更加完善的要素市场化配置体制机制的意见》(2020.3) 数据成为土地、劳动力、…...
Docker之Centos安装
介绍 Docker官方建议在Ubuntu中安装,因为Docker是基于Ubuntu发布的, 而且一般Docker出现的问题Ubuntu是最先更新或者打补丁的。 在很多版本的CentOS中是不支持更新最新的一些补丁包的。由于我们学习的环境都使用的是CentOS,因此这里我们将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 的一些主要知识点: 1. 加密和解密:Java Security 提供了一组加密和解密 API,可以实现各种加密标准,如 AES、DES、RSA 等。 2. 数字签名…...
了解web3,什么是web3
Web3是指下一代互联网,它基于区块链技术,将各种在线活动更加安全、透明和去中心化。Web3是一个广义的概念,它包括了很多方面,如数字货币、去中心化应用、智能合约等等。听不懂且大多数人听到这个东西,直觉感觉就像骗子…...
Harbor企业级Registry基础镜像仓库的详细安装使用教程(保姆级)
Harbor Docker 官方提供的私有仓库 registry,用起来虽然简单 ,但在管理的功能上存在不足。 Harbor是vmware一个用于存储和分发Docker镜像的企业级Registry服务器,harbor使用的是官方的docker registry(v2命名是distribution)服务去完成。 ha…...
Linux系统下数据同步服务RSYNC
一、RSYNC概述 1、什么是rsync rsync的好姐妹 sync 同步:刷新文件系统缓存,强制将修改过的数据块写入磁盘,并且更新超级块。 async 异步:将数据先放到缓冲区,再周期性(一般是30s)的去同步到磁…...
Docker介绍及其常用命令
Docker是一种容器化技术,可以打包应用程序及其依赖项,并将其作为独立的进程运行。它实现了操作系统级别的虚拟化,允许不同容器之间相互隔离,同时提高了应用程序的可移植性和安全性。Docker可以快速部署和扩展应用程序,…...
SwissArmyTransformer瑞士军刀工具箱使用手册
Introduction sat(SwissArmyTransformer)是一个灵活而强大的库,用于开发您自己的Transformer变体。 sat是以“瑞士军刀”命名的,这意味着所有型号(例如BERT、GPT、T5、GLM、CogView、ViT…)共享相同的backo…...
unity【动画】脚本_角色动画控制器 c#
首先创建一个代码文件夹Scripts 从人物角色Player的基类开始 创建IPlayer类 首先我们考虑到如果不挂载MonoBehaviour需要将角色设置成预制体实例化到场景上十分麻烦, 所以我们采用继承MonoBehaviour类的角色基类方法写代码 也就是说这个脚本直接绑定在角色物体…...
Java代码如何对Excel文件进行zip压缩
1:新建 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网络连接正常,但是无法正常上网
前言: 这个是一个win11的bug,好多人都遇到了,在孜孜不倦的百度下,毫无收获,终于是在抖音上看到有人分享的经验而解决了这个问题。 找到internet选项,然后点击打开 选择连接 将代理服务器中,为…...
硬科技企业社区“曲率引擎”品牌正式发布
“曲率引擎”,是科幻作品中最硬核的加速系统,通过改变时空的曲率,可实现光速飞行甚至能够超越光速。11月3日,“曲率引擎(warp drive)”作为硬科技企业社区品牌,在2023全球硬科技创新大会上正式对…...
少儿编程 2023年9月中国电子学会图形化编程等级考试Scratch编程三级真题解析(判断题)
2023年9月scratch编程等级考试三级真题 判断题(共10题,每题2分,共20分) 19、运行程序后,“我的变量”的值为25 答案:对 考点分析:考查积木综合使用,重点考查变量和运算积木的使用 开始我的变量为50,执行完第二行代码我的变量变为49,条件不成立执行否则语句,所以…...
MCU常见通信总线串讲(二)—— RS232和RS485
🙌秋名山码民的主页 😂oi退役选手,Java、大数据、单片机、IoT均有所涉猎,热爱技术,技术无罪 🎉欢迎关注🔎点赞👍收藏⭐️留言📝 获取源码,添加WX 目录 前言一…...
LazyVim: 将 Neovim 升级为完整 IDE | 开源日报 No.67
curl/curl Stars: 31.5k License: NOASSERTION Curl 是一个命令行工具,用于通过 URL 语法传输数据。 核心优势和关键特点包括: 可在命令行中方便地进行数据传输支持多种协议 (HTTP、FTP 等)提供丰富的选项和参数来满足不同需求 kubernetes/ingress-n…...
Java 语言特性(面试系列1)
一、面向对象编程 1. 封装(Encapsulation) 定义:将数据(属性)和操作数据的方法绑定在一起,通过访问控制符(private、protected、public)隐藏内部实现细节。示例: public …...
在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能
下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能,包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...
Vue3 + Element Plus + TypeScript中el-transfer穿梭框组件使用详解及示例
使用详解 Element Plus 的 el-transfer 组件是一个强大的穿梭框组件,常用于在两个集合之间进行数据转移,如权限分配、数据选择等场景。下面我将详细介绍其用法并提供一个完整示例。 核心特性与用法 基本属性 v-model:绑定右侧列表的值&…...
【JVM】- 内存结构
引言 JVM:Java Virtual Machine 定义:Java虚拟机,Java二进制字节码的运行环境好处: 一次编写,到处运行自动内存管理,垃圾回收的功能数组下标越界检查(会抛异常,不会覆盖到其他代码…...
【第二十一章 SDIO接口(SDIO)】
第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...
镜像里切换为普通用户
如果你登录远程虚拟机默认就是 root 用户,但你不希望用 root 权限运行 ns-3(这是对的,ns3 工具会拒绝 root),你可以按以下方法创建一个 非 root 用户账号 并切换到它运行 ns-3。 一次性解决方案:创建非 roo…...
相机从app启动流程
一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...
工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配
AI3D视觉的工业赋能者 迁移科技成立于2017年,作为行业领先的3D工业相机及视觉系统供应商,累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成,通过稳定、易用、高回报的AI3D视觉系统,为汽车、新能源、金属制造等行…...
中医有效性探讨
文章目录 西医是如何发展到以生物化学为药理基础的现代医学?传统医学奠基期(远古 - 17 世纪)近代医学转型期(17 世纪 - 19 世纪末)现代医学成熟期(20世纪至今) 中医的源远流长和一脉相承远古至…...
R语言速释制剂QBD解决方案之三
本文是《Quality by Design for ANDAs: An Example for Immediate-Release Dosage Forms》第一个处方的R语言解决方案。 第一个处方研究评估原料药粒径分布、MCC/Lactose比例、崩解剂用量对制剂CQAs的影响。 第二处方研究用于理解颗粒外加硬脂酸镁和滑石粉对片剂质量和可生产…...
