当前位置: 首页 > 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…...

深度学习在微纳光子学中的应用

深度学习在微纳光子学中的主要应用方向 深度学习与微纳光子学的结合主要集中在以下几个方向&#xff1a; 逆向设计 通过神经网络快速预测微纳结构的光学响应&#xff0c;替代传统耗时的数值模拟方法。例如设计超表面、光子晶体等结构。 特征提取与优化 从复杂的光学数据中自…...

无法与IP建立连接,未能下载VSCode服务器

如题&#xff0c;在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈&#xff0c;发现是VSCode版本自动更新惹的祸&#xff01;&#xff01;&#xff01; 在VSCode的帮助->关于这里发现前几天VSCode自动更新了&#xff0c;我的版本号变成了1.100.3 才导致了远程连接出…...

多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验

一、多模态商品数据接口的技术架构 &#xff08;一&#xff09;多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如&#xff0c;当用户上传一张“蓝色连衣裙”的图片时&#xff0c;接口可自动提取图像中的颜色&#xff08;RGB值&…...

《通信之道——从微积分到 5G》读书总结

第1章 绪 论 1.1 这是一本什么样的书 通信技术&#xff0c;说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号&#xff08;调制&#xff09; 把信息从信号中抽取出来&am…...

【算法训练营Day07】字符串part1

文章目录 反转字符串反转字符串II替换数字 反转字符串 题目链接&#xff1a;344. 反转字符串 双指针法&#xff0c;两个指针的元素直接调转即可 class Solution {public void reverseString(char[] s) {int head 0;int end s.length - 1;while(head < end) {char temp …...

【生成模型】视频生成论文调研

工作清单 上游应用方向&#xff1a;控制、速度、时长、高动态、多主体驱动 类型工作基础模型WAN / WAN-VACE / HunyuanVideo控制条件轨迹控制ATI~镜头控制ReCamMaster~多主体驱动Phantom~音频驱动Let Them Talk: Audio-Driven Multi-Person Conversational Video Generation速…...

推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材)

推荐 github 项目:GeminiImageApp(图片生成方向&#xff0c;可以做一定的素材) 这个项目能干嘛? 使用 gemini 2.0 的 api 和 google 其他的 api 来做衍生处理 简化和优化了文生图和图生图的行为(我的最主要) 并且有一些目标检测和切割(我用不到) 视频和 imagefx 因为没 a…...

20个超级好用的 CSS 动画库

分享 20 个最佳 CSS 动画库。 它们中的大多数将生成纯 CSS 代码&#xff0c;而不需要任何外部库。 1.Animate.css 一个开箱即用型的跨浏览器动画库&#xff0c;可供你在项目中使用。 2.Magic Animations CSS3 一组简单的动画&#xff0c;可以包含在你的网页或应用项目中。 3.An…...

如何更改默认 Crontab 编辑器 ?

在 Linux 领域中&#xff0c;crontab 是您可能经常遇到的一个术语。这个实用程序在类 unix 操作系统上可用&#xff0c;用于调度在预定义时间和间隔自动执行的任务。这对管理员和高级用户非常有益&#xff0c;允许他们自动执行各种系统任务。 编辑 Crontab 文件通常使用文本编…...

深度剖析 DeepSeek 开源模型部署与应用:策略、权衡与未来走向

在人工智能技术呈指数级发展的当下&#xff0c;大模型已然成为推动各行业变革的核心驱动力。DeepSeek 开源模型以其卓越的性能和灵活的开源特性&#xff0c;吸引了众多企业与开发者的目光。如何高效且合理地部署与运用 DeepSeek 模型&#xff0c;成为释放其巨大潜力的关键所在&…...