树形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…...
conda相比python好处
Conda 作为 Python 的环境和包管理工具,相比原生 Python 生态(如 pip 虚拟环境)有许多独特优势,尤其在多项目管理、依赖处理和跨平台兼容性等方面表现更优。以下是 Conda 的核心好处: 一、一站式环境管理:…...
Qt Widget类解析与代码注释
#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this); }Widget::~Widget() {delete ui; }//解释这串代码,写上注释 当然可以!这段代码是 Qt …...
HTML 列表、表格、表单
1 列表标签 作用:布局内容排列整齐的区域 列表分类:无序列表、有序列表、定义列表。 例如: 1.1 无序列表 标签:ul 嵌套 li,ul是无序列表,li是列表条目。 注意事项: ul 标签里面只能包裹 li…...
在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module
1、为什么要修改 CONNECT 报文? 多租户隔离:自动为接入设备追加租户前缀,后端按 ClientID 拆分队列。零代码鉴权:将入站用户名替换为 OAuth Access-Token,后端 Broker 统一校验。灰度发布:根据 IP/地理位写…...
macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用
文章目录 问题现象问题原因解决办法 问题现象 macOS启动台(Launchpad)多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显,都是Google家的办公全家桶。这些应用并不是通过独立安装的…...
苍穹外卖--缓存菜品
1.问题说明 用户端小程序展示的菜品数据都是通过查询数据库获得,如果用户端访问量比较大,数据库访问压力随之增大 2.实现思路 通过Redis来缓存菜品数据,减少数据库查询操作。 缓存逻辑分析: ①每个分类下的菜品保持一份缓存数据…...
Matlab | matlab常用命令总结
常用命令 一、 基础操作与环境二、 矩阵与数组操作(核心)三、 绘图与可视化四、 编程与控制流五、 符号计算 (Symbolic Math Toolbox)六、 文件与数据 I/O七、 常用函数类别重要提示这是一份 MATLAB 常用命令和功能的总结,涵盖了基础操作、矩阵运算、绘图、编程和文件处理等…...
【OSG学习笔记】Day 16: 骨骼动画与蒙皮(osgAnimation)
骨骼动画基础 骨骼动画是 3D 计算机图形中常用的技术,它通过以下两个主要组件实现角色动画。 骨骼系统 (Skeleton):由层级结构的骨头组成,类似于人体骨骼蒙皮 (Mesh Skinning):将模型网格顶点绑定到骨骼上,使骨骼移动…...
html-<abbr> 缩写或首字母缩略词
定义与作用 <abbr> 标签用于表示缩写或首字母缩略词,它可以帮助用户更好地理解缩写的含义,尤其是对于那些不熟悉该缩写的用户。 title 属性的内容提供了缩写的详细说明。当用户将鼠标悬停在缩写上时,会显示一个提示框。 示例&#x…...
基于Java Swing的电子通讯录设计与实现:附系统托盘功能代码详解
JAVASQL电子通讯录带系统托盘 一、系统概述 本电子通讯录系统采用Java Swing开发桌面应用,结合SQLite数据库实现联系人管理功能,并集成系统托盘功能提升用户体验。系统支持联系人的增删改查、分组管理、搜索过滤等功能,同时可以最小化到系统…...
