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(格斯特纳波)
一.格斯特纳波 要让水面动起来,必须要保证平面有足够的三角面。我们可以在材质里的细节面板打开曲面细分,可以分裂三角面且使之数量更多,选择“扁平曲面细分,其作用是切割我的三角面,然后给我做一大堆三角面出来。 这…...
线程同步:确保多线程程序的安全与高效!
全文目录: 开篇语前序前言第一部分:线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分:synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分ÿ…...
DAY 47
三、通道注意力 3.1 通道注意力的定义 # 新增:通道注意力模块(SE模块) class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...
学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1
每日一言 生活的美好,总是藏在那些你咬牙坚持的日子里。 硬件:OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写,"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...
Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决
Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决 问题背景 在一个基于 Spring Cloud Gateway WebFlux 构建的微服务项目中,新增了一个本地验证码接口 /code,使用函数式路由(RouterFunction)和 Hutool 的 Circle…...
C# 求圆面积的程序(Program to find area of a circle)
给定半径r,求圆的面积。圆的面积应精确到小数点后5位。 例子: 输入:r 5 输出:78.53982 解释:由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982,因为我们只保留小数点后 5 位数字。 输…...
JVM 内存结构 详解
内存结构 运行时数据区: Java虚拟机在运行Java程序过程中管理的内存区域。 程序计数器: 线程私有,程序控制流的指示器,分支、循环、跳转、异常处理、线程恢复等基础功能都依赖这个计数器完成。 每个线程都有一个程序计数…...
排序算法总结(C++)
目录 一、稳定性二、排序算法选择、冒泡、插入排序归并排序随机快速排序堆排序基数排序计数排序 三、总结 一、稳定性 排序算法的稳定性是指:同样大小的样本 **(同样大小的数据)**在排序之后不会改变原始的相对次序。 稳定性对基础类型对象…...
JS手写代码篇----使用Promise封装AJAX请求
15、使用Promise封装AJAX请求 promise就有reject和resolve了,就不必写成功和失败的回调函数了 const BASEURL ./手写ajax/test.jsonfunction promiseAjax() {return new Promise((resolve, reject) > {const xhr new XMLHttpRequest();xhr.open("get&quo…...
腾讯云V3签名
想要接入腾讯云的Api,必然先按其文档计算出所要求的签名。 之前也调用过腾讯云的接口,但总是卡在签名这一步,最后放弃选择SDK,这次终于自己代码实现。 可能腾讯云翻新了接口文档,现在阅读起来,清晰了很多&…...
jmeter聚合报告中参数详解
sample、average、min、max、90%line、95%line,99%line、Error错误率、吞吐量Thoughput、KB/sec每秒传输的数据量 sample(样本数) 表示测试中发送的请求数量,即测试执行了多少次请求。 单位,以个或者次数表示。 示例:…...
