Codeforces Round 646 (Div. 2) E. Tree Shuffling(树,贪心)
题目链接
Codeforces Round 646 (Div. 2) E. Tree Shuffling
思路
考虑一个节点 u u u,显然它子树中的操作可以由它本身和祖先来进行。如果它的祖先有比它花费更小的,直接跳过节点 u u u。
我们分别记录每一个子树中位置不对的 0 0 0和 1 1 1的个数,每次操作选出较小的那一个即可。
代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
typedef pair<int, int> pii;
const int N = 2e5 + 5, M = 1e6 + 5;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f3f3f3f3f;int n, ans;
int a[N], b[N], c[N], cnt[N][2], dp[N];
vector<int>mp[N];
void dfs(int u, int fu)
{if (b[u] != c[u])cnt[u][b[u]]++;for (int j : mp[u]){if (j == fu) continue;dfs(j, u);cnt[u][0] += cnt[j][0], cnt[u][1] += cnt[j][1];}
}
void dfs1(int u, int fu)
{dp[u] = a[u] * min(cnt[u][0], cnt[u][1]) * 2;for (int j : mp[u]){if (j == fu) continue;dfs1(j, u);}
}
void dfs2(int u, int fu, int minn)
{if (minn > a[u]){if (minn != inf){ans -= min(cnt[u][0], cnt[u][1]) * 2 * minn;}ans += dp[u];minn = a[u];}for (int j : mp[u]){if (j == fu) continue;dfs2(j, u, minn);}
}
void solve()
{cin >> n;for (int i = 1; i <= n; i++){cin >> a[i] >> b[i] >> c[i];}for (int i = 1, u, v; i < n; i++){cin >> u >> v;mp[u].push_back(v);mp[v].push_back(u);}dfs(1, -1);if (cnt[1][0] != cnt[1][1]){cout << -1 << endl;return;}dfs1(1, -1);dfs2(1, -1, inf);cout << ans << endl;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int test = 1;// cin >> test;for (int i = 1; i <= test; i++){solve();}return 0;
}
相关文章:
Codeforces Round 646 (Div. 2) E. Tree Shuffling(树,贪心)
题目链接 Codeforces Round 646 (Div. 2) E. Tree Shuffling 思路 考虑一个节点 u u u,显然它子树中的操作可以由它本身和祖先来进行。如果它的祖先有比它花费更小的,直接跳过节点 u u u。 我们分别记录每一个子树中位置不对的 0 0 0和 1 1 1的个数&…...
HCIE-Datacom题库_11_IPsecVPN【17道题】
一、单选题 1.IPsecSA(SecurityAssociation,安全联盟)有两种生成方式,分别是手工方式和IKE自动协商方式,以下关于这两种方式的描述中,错误的是哪一项? 手工方式和IKE方式建立的SA都支持动态刷新 IKE方式建立的SA,其生存周期由…...
Dongle Sentinal在Jenkins下访问不了的问题
背景: 工作站部署的jenkins的脚本无法正常打包,定位后发现是本地获取不了license,但是使用usb over network的远程license都能获取并正常打包 分析: 获取不了license的原因是本地无法识别dongle。根据提供信息,之前…...
X射线衍射(X-ray Diffraction,XRD)小白版
文章目录 实验过程原理晶体构成X射线波长diffraction 干涉效应 Braggs Law晶体间距d散射角度θ半波长λ/2公式 公式名称由来应用设备 实验过程 In the X-ray experiment , a sample is placed into the center of an instrument and illuminated with a beam of X-rays. 在X射…...
Nordic 定时器系统app timer[获取时间戳]
获取时间戳 想要在Nordic 定时器系统中获取时间戳,也就是是在调用app_timer的时候时间戳要有效,我们可以看看定时器系统初始化: ret_code_t app_timer_init(void) {ret_code_t err_code;drv_rtc_config_t config {.prescaler APP_TIMER_CONFIG_RTC_FREQUENCY,.int…...
【Linux】实验:mkdir 命令 、 tee 命令
#1024程序员节|征文# 1.命令说明 本文主要实验 linux 的两个命令:mkdir -p 路径、 tee 创建文件。 命令:mkdir -p 路径 说明:该命令将自动创建路径下的目录及子目录,结尾可以/ 也可以不带/,默认都是建文…...
asp.net core mvc发布时输出视图文件Views
var builder WebApplication.CreateBuilder(args); builder.Services.AddRazorPages();builder.Services.AddControllersWithViews(ops > {//全局异常过滤器,注册ops.Filters.Add<ExceptionFilter>(); })// Views视图文件输出到发布目录,视图文…...
服务器模块测试
目录 测试逻辑 测试工具 测试 测试逻辑 我们可以使用一个简单的业务处理逻辑来进行测试。 最简单的,我们业务逻辑就直接返回一个固定的字符串 void Message(const PtrConnection&con,Buffer* inbuffer) //模拟用户新数据回调 {inbuffer->MoveReadOf…...
ATTCK 框架讲解
摘要 ATT&CK框架作为MITRE公司开发的网络攻击行为知识库,自2015年发布以来,已成为信息安全领域的重要工具。该框架通过提炼和归纳真实世界中的网络威胁事件,以攻击者的视角构建了一套系统化的战术和技术分类体系。本文详细阐述了ATT&…...
ADC在STM32F1系列的使用详解
目录 1. ADC简介 2. 逐次逼近型ADC(ADC0809) 3. ADC框图(STM32) 4. ADC基本结构 5. 输入通道 6. 转换模式 6.1 单次转换 6.1.1 非扫描模式 6.1.2 扫描模式 6.2 连续转换 6.2.1 非扫描模式 6.2.2 扫描模式…...
网络空间安全之一个WH的超前沿全栈技术深入学习之路(一:渗透测试行业术语扫盲)作者——LJS
欢迎各位彦祖与热巴畅游本人专栏与博客 你的三连是我最大的动力 以下图片仅代表专栏特色 [点击箭头指向的专栏名即可闪现] 专栏跑道一 ➡️网络空间安全——全栈前沿技术持续深入学习 专栏跑道二➡️ 24 Network Security -LJS 专栏跑道三 ➡️ MYSQL REDIS Advanc…...
中间件-概念
什么是中间件? 中间件(Middleware)是位于 Web 服务器和应用程序之间的组件,它可以处理每个请求和响应。中间件的主要作用是在请求到达应用程序之前或响应返回客户端之前对其进行处理。中间件可以执行各种任务,如日志记…...
vscode离线状态ssh连接不断输入密码登不上:配置commit_id
如题,vscode在一个离线服务器上,通过remote-ssh登录远程服务器,不断弹出密码框,总是进不去,后来了解到主要是不同vscode版本需要下载对应抑制commit-id的vscode-server-linux-x64.tar.gz包。 1)vscode, 点…...
Vim使用与进阶
1. Vim 技巧 撤销 U 反撤销 Ctrl U 历史命令 history 2.要在Vim中进行多行缩进,可以按以下步骤操作: 进入Vim编辑器并进入命令模式。使用 v 键或 Shift v 键选择多行需要缩进的文本。按下 > 键进行向右缩进,或按下 < 键进行向左…...
python中frida的安装+frida-server(雷电模拟器)保姆级安装教程
一.安装雷电模拟器 雷电模拟器官网 直接下载安装即可 (1)打开必要权限 雷电模拟器的设置已完毕 二.安装adb工具 本文以autox.js来实现adb操作 (1)vscode中下载auto.js插件 (2)雷电模拟器下载autox.j…...
Java线程安全集合之COW
概述 java.util.concurrent.CopyOnWriteArrayList写时复制顺序表,一种采用写时复制技术(COW)实现的线程安全的顺序表,可代替java.util.ArrayList用于并发环境中。写时复制,在写入时,会复制顺序表的新副本&…...
智能汽车制造:海康NVR管理平台/工具EasyNVR多品牌NVR管理工具/设备实现无插件视频监控直播方案
一、背景介绍 近年来,随着网络在我国的普及和深化发展,企业的信息化建设不断深入,各行各业都加快了信息网络平台的建设,大多数单位已经或者正在铺设企业内部的计算机局域网。与此同时,网络也成为先进的新兴应用提供了…...
[渗透]前端源码Chrome浏览器修改并运行
文章目录 简述本项目所使用的代码[Fir](https://so.csdn.net/so/search?qFir&spm1001.2101.3001.7020) Cloud 完整项目 原始页面修改源码本地运行前端源码修改页面布局修改请求接口 本项目请求方式 简述 好久之前,就已经看到,_无论什么样的加密&am…...
SAP揭秘者-怎么查看SAP 版本及S4 HANA的版本
文章摘要: 在给客户实施SAP项目或部署SAP服务器及SAP跟外部系统集成时,经常客户或第三方软件公司会问SAP版本或SAP HANA的版本。那么到底怎么来看这个SAP的版本呢?这个问题其实很多SAP模块顾问都不知道怎么看,你可以想象一下&…...
UE4 材质学习笔记13(格斯特纳波)
一.格斯特纳波 要让水面动起来,必须要保证平面有足够的三角面。我们可以在材质里的细节面板打开曲面细分,可以分裂三角面且使之数量更多,选择“扁平曲面细分,其作用是切割我的三角面,然后给我做一大堆三角面出来。 这…...
【AI学习】三、AI算法中的向量
在人工智能(AI)算法中,向量(Vector)是一种将现实世界中的数据(如图像、文本、音频等)转化为计算机可处理的数值型特征表示的工具。它是连接人类认知(如语义、视觉特征)与…...
Psychopy音频的使用
Psychopy音频的使用 本文主要解决以下问题: 指定音频引擎与设备;播放音频文件 本文所使用的环境: Python3.10 numpy2.2.6 psychopy2025.1.1 psychtoolbox3.0.19.14 一、音频配置 Psychopy文档链接为Sound - for audio playback — Psy…...
关键领域软件测试的突围之路:如何破解安全与效率的平衡难题
在数字化浪潮席卷全球的今天,软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件,这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下,实现高效测试与快速迭代?这一命题正考验着…...
短视频矩阵系统文案创作功能开发实践,定制化开发
在短视频行业迅猛发展的当下,企业和个人创作者为了扩大影响力、提升传播效果,纷纷采用短视频矩阵运营策略,同时管理多个平台、多个账号的内容发布。然而,频繁的文案创作需求让运营者疲于应对,如何高效产出高质量文案成…...
AGain DB和倍数增益的关系
我在设置一款索尼CMOS芯片时,Again增益0db变化为6DB,画面的变化只有2倍DN的增益,比如10变为20。 这与dB和线性增益的关系以及传感器处理流程有关。以下是具体原因分析: 1. dB与线性增益的换算关系 6dB对应的理论线性增益应为&…...
FFmpeg:Windows系统小白安装及其使用
一、安装 1.访问官网 Download FFmpeg 2.点击版本目录 3.选择版本点击安装 注意这里选择的是【release buids】,注意左上角标题 例如我安装在目录 F:\FFmpeg 4.解压 5.添加环境变量 把你解压后的bin目录(即exe所在文件夹)加入系统变量…...
深度学习之模型压缩三驾马车:模型剪枝、模型量化、知识蒸馏
一、引言 在深度学习中,我们训练出的神经网络往往非常庞大(比如像 ResNet、YOLOv8、Vision Transformer),虽然精度很高,但“太重”了,运行起来很慢,占用内存大,不适合部署到手机、摄…...
[论文阅读]TrustRAG: Enhancing Robustness and Trustworthiness in RAG
TrustRAG: Enhancing Robustness and Trustworthiness in RAG [2501.00879] TrustRAG: Enhancing Robustness and Trustworthiness in Retrieval-Augmented Generation 代码:HuichiZhou/TrustRAG: Code for "TrustRAG: Enhancing Robustness and Trustworthin…...
Visual Studio Code 扩展
Visual Studio Code 扩展 change-case 大小写转换EmmyLua for VSCode 调试插件Bookmarks 书签 change-case 大小写转换 https://marketplace.visualstudio.com/items?itemNamewmaurer.change-case 选中单词后,命令 changeCase.commands 可预览转换效果 EmmyLua…...
【把数组变成一棵树】有序数组秒变平衡BST,原来可以这么优雅!
【把数组变成一棵树】有序数组秒变平衡BST,原来可以这么优雅! 🌱 前言:一棵树的浪漫,从数组开始说起 程序员的世界里,数组是最常见的基本结构之一,几乎每种语言、每种算法都少不了它。可你有没有想过,一组看似“线性排列”的有序数组,竟然可以**“长”成一棵平衡的二…...
