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

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&#xff0c;显然它子树中的操作可以由它本身和祖先来进行。如果它的祖先有比它花费更小的&#xff0c;直接跳过节点 u u u。 我们分别记录每一个子树中位置不对的 0 0 0和 1 1 1的个数&…...

HCIE-Datacom题库_11_IPsecVPN【17道题】

一、单选题 1.IPsecSA(SecurityAssociation&#xff0c;安全联盟)有两种生成方式&#xff0c;分别是手工方式和IKE自动协商方式&#xff0c;以下关于这两种方式的描述中&#xff0c;错误的是哪一项? 手工方式和IKE方式建立的SA都支持动态刷新 IKE方式建立的SA,其生存周期由…...

Dongle Sentinal在Jenkins下访问不了的问题

背景&#xff1a; 工作站部署的jenkins的脚本无法正常打包&#xff0c;定位后发现是本地获取不了license&#xff0c;但是使用usb over network的远程license都能获取并正常打包 分析&#xff1a; 获取不了license的原因是本地无法识别dongle。根据提供信息&#xff0c;之前…...

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程序员节&#xff5c;征文# 1.命令说明 本文主要实验 linux 的两个命令&#xff1a;mkdir -p 路径、 tee 创建文件。 命令&#xff1a;mkdir -p 路径 说明&#xff1a;该命令将自动创建路径下的目录及子目录&#xff0c;结尾可以/ 也可以不带/&#xff0c;默认都是建文…...

asp.net core mvc发布时输出视图文件Views

var builder WebApplication.CreateBuilder(args); builder.Services.AddRazorPages();builder.Services.AddControllersWithViews(ops > {//全局异常过滤器&#xff0c;注册ops.Filters.Add<ExceptionFilter>(); })// Views视图文件输出到发布目录&#xff0c;视图文…...

服务器模块测试

目录 测试逻辑 测试工具 测试 测试逻辑 我们可以使用一个简单的业务处理逻辑来进行测试。 最简单的&#xff0c;我们业务逻辑就直接返回一个固定的字符串 void Message(const PtrConnection&con,Buffer* inbuffer) //模拟用户新数据回调 {inbuffer->MoveReadOf…...

ATTCK 框架讲解

摘要 ATT&CK框架作为MITRE公司开发的网络攻击行为知识库&#xff0c;自2015年发布以来&#xff0c;已成为信息安全领域的重要工具。该框架通过提炼和归纳真实世界中的网络威胁事件&#xff0c;以攻击者的视角构建了一套系统化的战术和技术分类体系。本文详细阐述了ATT&…...

ADC在STM32F1系列的使用详解

目录 1. ADC简介 2. 逐次逼近型ADC&#xff08;ADC0809&#xff09; 3. ADC框图&#xff08;STM32&#xff09; 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…...

中间件-概念

什么是中间件&#xff1f; 中间件&#xff08;Middleware&#xff09;是位于 Web 服务器和应用程序之间的组件&#xff0c;它可以处理每个请求和响应。中间件的主要作用是在请求到达应用程序之前或响应返回客户端之前对其进行处理。中间件可以执行各种任务&#xff0c;如日志记…...

vscode离线状态ssh连接不断输入密码登不上:配置commit_id

如题&#xff0c;vscode在一个离线服务器上&#xff0c;通过remote-ssh登录远程服务器&#xff0c;不断弹出密码框&#xff0c;总是进不去&#xff0c;后来了解到主要是不同vscode版本需要下载对应抑制commit-id的vscode-server-linux-x64.tar.gz包。 1&#xff09;vscode, 点…...

Vim使用与进阶

1. Vim 技巧 撤销 U 反撤销 Ctrl U 历史命令 history 2.要在Vim中进行多行缩进&#xff0c;可以按以下步骤操作&#xff1a; 进入Vim编辑器并进入命令模式。使用 v 键或 Shift v 键选择多行需要缩进的文本。按下 > 键进行向右缩进&#xff0c;或按下 < 键进行向左…...

python中frida的安装+frida-server(雷电模拟器)保姆级安装教程

一.安装雷电模拟器 雷电模拟器官网 直接下载安装即可 &#xff08;1&#xff09;打开必要权限 雷电模拟器的设置已完毕 二.安装adb工具 本文以autox.js来实现adb操作 &#xff08;1&#xff09;vscode中下载auto.js插件 &#xff08;2&#xff09;雷电模拟器下载autox.j…...

Java线程安全集合之COW

概述 java.util.concurrent.CopyOnWriteArrayList写时复制顺序表&#xff0c;一种采用写时复制技术&#xff08;COW&#xff09;实现的线程安全的顺序表&#xff0c;可代替java.util.ArrayList用于并发环境中。写时复制&#xff0c;在写入时&#xff0c;会复制顺序表的新副本&…...

智能汽车制造:海康NVR管理平台/工具EasyNVR多品牌NVR管理工具/设备实现无插件视频监控直播方案

一、背景介绍 近年来&#xff0c;随着网络在我国的普及和深化发展&#xff0c;企业的信息化建设不断深入&#xff0c;各行各业都加快了信息网络平台的建设&#xff0c;大多数单位已经或者正在铺设企业内部的计算机局域网。与此同时&#xff0c;网络也成为先进的新兴应用提供了…...

[渗透]前端源码Chrome浏览器修改并运行

文章目录 简述本项目所使用的代码[Fir](https://so.csdn.net/so/search?qFir&spm1001.2101.3001.7020) Cloud 完整项目 原始页面修改源码本地运行前端源码修改页面布局修改请求接口 本项目请求方式 简述 好久之前&#xff0c;就已经看到&#xff0c;_无论什么样的加密&am…...

SAP揭秘者-怎么查看SAP 版本及S4 HANA的版本

文章摘要&#xff1a; 在给客户实施SAP项目或部署SAP服务器及SAP跟外部系统集成时&#xff0c;经常客户或第三方软件公司会问SAP版本或SAP HANA的版本。那么到底怎么来看这个SAP的版本呢&#xff1f;这个问题其实很多SAP模块顾问都不知道怎么看&#xff0c;你可以想象一下&…...

UE4 材质学习笔记13(格斯特纳波)

一.格斯特纳波 要让水面动起来&#xff0c;必须要保证平面有足够的三角面。我们可以在材质里的细节面板打开曲面细分&#xff0c;可以分裂三角面且使之数量更多&#xff0c;选择“扁平曲面细分&#xff0c;其作用是切割我的三角面&#xff0c;然后给我做一大堆三角面出来。 这…...

IDEA运行Tomcat出现乱码问题解决汇总

最近正值期末周&#xff0c;有很多同学在写期末Java web作业时&#xff0c;运行tomcat出现乱码问题&#xff0c;经过多次解决与研究&#xff0c;我做了如下整理&#xff1a; 原因&#xff1a; IDEA本身编码与tomcat的编码与Windows编码不同导致&#xff0c;Windows 系统控制台…...

Docker 离线安装指南

参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性&#xff0c;不同版本的Docker对内核版本有不同要求。例如&#xff0c;Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本&#xff0c;Docker17.09及更高版本对应Linux内核4.9.x及更高版本。…...

CTF show Web 红包题第六弹

提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框&#xff0c;很难让人不联想到SQL注入&#xff0c;但提示都说了不是SQL注入&#xff0c;所以就不往这方面想了 ​ 先查看一下网页源码&#xff0c;发现一段JavaScript代码&#xff0c;有一个关键类ctfs…...

前端倒计时误差!

提示:记录工作中遇到的需求及解决办法 文章目录 前言一、误差从何而来?二、五大解决方案1. 动态校准法(基础版)2. Web Worker 计时3. 服务器时间同步4. Performance API 高精度计时5. 页面可见性API优化三、生产环境最佳实践四、终极解决方案架构前言 前几天听说公司某个项…...

PL0语法,分析器实现!

简介 PL/0 是一种简单的编程语言,通常用于教学编译原理。它的语法结构清晰,功能包括常量定义、变量声明、过程(子程序)定义以及基本的控制结构(如条件语句和循环语句)。 PL/0 语法规范 PL/0 是一种教学用的小型编程语言,由 Niklaus Wirth 设计,用于展示编译原理的核…...

自然语言处理——Transformer

自然语言处理——Transformer 自注意力机制多头注意力机制Transformer 虽然循环神经网络可以对具有序列特性的数据非常有效&#xff0c;它能挖掘数据中的时序信息以及语义信息&#xff0c;但是它有一个很大的缺陷——很难并行化。 我们可以考虑用CNN来替代RNN&#xff0c;但是…...

大语言模型(LLM)中的KV缓存压缩与动态稀疏注意力机制设计

随着大语言模型&#xff08;LLM&#xff09;参数规模的增长&#xff0c;推理阶段的内存占用和计算复杂度成为核心挑战。传统注意力机制的计算复杂度随序列长度呈二次方增长&#xff0c;而KV缓存的内存消耗可能高达数十GB&#xff08;例如Llama2-7B处理100K token时需50GB内存&a…...

【MATLAB代码】基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),附源代码|订阅专栏后可直接查看

文章所述的代码实现了基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),针对传感器观测数据中存在的脉冲型异常噪声问题,通过非线性加权机制提升滤波器的抗干扰能力。代码通过对比传统KF与MCC-KF在含异常值场景下的表现,验证了后者在状态估计鲁棒性方面的显著优…...

嵌入式学习之系统编程(九)OSI模型、TCP/IP模型、UDP协议网络相关编程(6.3)

目录 一、网络编程--OSI模型 二、网络编程--TCP/IP模型 三、网络接口 四、UDP网络相关编程及主要函数 ​编辑​编辑 UDP的特征 socke函数 bind函数 recvfrom函数&#xff08;接收函数&#xff09; sendto函数&#xff08;发送函数&#xff09; 五、网络编程之 UDP 用…...

DAY 26 函数专题1

函数定义与参数知识点回顾&#xff1a;1. 函数的定义2. 变量作用域&#xff1a;局部变量和全局变量3. 函数的参数类型&#xff1a;位置参数、默认参数、不定参数4. 传递参数的手段&#xff1a;关键词参数5 题目1&#xff1a;计算圆的面积 任务&#xff1a; 编写一…...