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

根能抵达的节点(二分法、DFS)C++

给定一棵由 N个节点构成的带边权树。节点编号从 0到 N−1,其中 0 号点为根节点。最初,从根节点可以抵达所有节点(包括自己)。如果我们将所有边权小于 X 的边全部删掉,那么从根节点可以抵达的节点数目就可能发生改变。
现在,给定一个整数 Y,请你找到最小的非负整数 X,使得所有边权小于 X
的边都被删掉以后,根节点能够抵达的节点数目(包括自己)不超过 Y

输入格式
第一行包含整数 T,表示共有 T 组测试数据。每组数据第一行包含两个整数 N,Y。
接下来 N−1行,每行包含三个整数 U,V,W,表示点 U 和点 V 之间存在一条权值为 W 的边。

输出格式
每组数据输出一行,一个 X。
注意,X 应不小于 0。

数据范围
1≤T≤100,
1≤N≤20000,
1≤Y≤N,
0≤U,V<N,
0≤W≤107,

保证在一个测试点中,所有 N 的和不超过 105。

输入样例:
2
3 2
0 1 2
0 2 3

6 3
0 1 8
0 2 3
1 3 2
1 4 5
2 5 6

输出样例:
3
4

#include<iostream>
#include<cstring>
using namespace std;
const int N=20010,M=N*2;
int h[N],e[M],ne[M],w[M],idx; //头结点、邻接表结点、指针、权、插入的第几个结点。
void add(int a,int b,int c)
{e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
int dfs(int u,int mid,int fa) //从第u个节点遍历,mid为答案,fa为父节点
{int res=1; //从父节点开始可以遍历到的节点for(int i=h[u];~i;i=ne[i]){int j=e[i];if(j==fa||w[i]<mid) continue;//如果次节点边权小于答案,说明该节点被删除后无法到达根节点。res+=dfs(j,mid,u);}return res;
}
int main()
{int T;cin>>T;while(T--){int n,y;cin>>n>>y;idx=0; //每次输出将邻接表清空memset(h,-1,sizeof(h));for(int i=0;i<n-1;i++){int a,b,c;cin>>a>>b>>c;add(a,b,c);  //树为特殊的无向图add(b,a,c);}int l=0,r=1e8;while(l<r){int mid=(l+r)/2;if(dfs(0,mid,-1)<=y) r=mid; //当答案小于y时说明答案在y左边,r=mid;else l=mid+1;}cout<<r<<endl;}return 0;
}

相关文章:

根能抵达的节点(二分法、DFS)C++

给定一棵由 N个节点构成的带边权树。节点编号从 0到 N−1&#xff0c;其中 0 号点为根节点。最初&#xff0c;从根节点可以抵达所有节点&#xff08;包括自己&#xff09;。如果我们将所有边权小于 X 的边全部删掉&#xff0c;那么从根节点可以抵达的节点数目就可能发生改变。 …...

一天一个设计模式---桥接模式

概念 桥接器模式是一种结构型设计模式&#xff0c;旨在将抽象部分与实现部分分离&#xff0c;使它们可以独立变化而不相互影响。桥接器模式通过创建一个桥接接口&#xff0c;连接抽象和实现&#xff0c;从而使两者可以独立演化。 具体内容 桥接器模式通常包括以下几个要素&a…...

OpenHarmony4.0Release系统应用常见问题FAQ

前言 自OpenHarmony4.0Release发布之后&#xff0c;许多小伙伴使用了配套的系统应用源码以及IDE作为基线开发&#xff0c;也遇到了各种各样的问题&#xff0c;这篇文档主要收录了比较常见的一些问题解答。 FAQ 系统应用源码在哪 目前OpenHarmony系统应用分为3种模式&#x…...

Skywalking UI页面中操作的各种实用功能汇总

刚刚接触skywalking不久&#xff0c;在这里总结一下在UI页面中操作的各种实用功能&#xff0c;随着使用的不断深入&#xff0c;我也会对文章进行持续补充。 本文skywalking 的ui入口是官方demo &#xff0c;版本是10.0.0-SNAPSHOT-593bd05 http://demo.skywalking.apache.org…...

springboot摄影跟拍预定管理系统源码和论文

首先,论文一开始便是清楚的论述了系统的研究内容。其次,剖析系统需求分析,弄明白“做什么”,分析包括业务分析和业务流程的分析以及用例分析,更进一步明确系统的需求。然后在明白了系统的需求基础上需要进一步地设计系统,主要包罗软件架构模式、整体功能模块、数据库设计。本项…...

【python】python新年烟花代码【附源码】

欢迎来到英杰社区https://bbs.csdn.net/topics/617804998 新年的钟声即将敲响&#xff0c;为了庆祝这个喜庆的时刻&#xff0c;我们可以用 Python 编写一个炫彩夺目的烟花盛典。本文将详细介绍如何使用 Pygame 库创建一个令人惊叹的烟花效果。 一、效果图&#xff1a; 二…...

书生·浦语大模型实战营-学习笔记1

目录 书生浦语大模型全链路开源体系数据集预训练微调评测部署多智能体 视频地址&#xff1a; (1)书生浦语大模型全链路开源体系 开源工具github&#xff1a; https://github.com/InternLM/InternLM 书生浦语大模型全链路开源体系 这次视频中介绍了由上海人工智能实验室OpenMMLa…...

ELF解析03 - 加载段

本文主要讨论 mmap 函数以及如何使用 mmap 函数来加载一个 ELF 的可加载段。 01纠错 Android 8 及以后是会读取 section header 的&#xff0c;但不是所有的 section 都会读取。 https://cs.android.com/android/platform/superproject/main//main:bionic/linker/linker_phdr…...

Mysql——索引相关的数据结构

索引 引入 我们知道&#xff0c;数据库查询是数据库的最主要功能之一。我们都希望查询数据的速度能尽可能的快&#xff0c;因此数据库系统的设计者会从查询算法的角度进行优化。最基本的查询算法当然是顺序查找&#xff08;linear search&#xff09;&#xff0c;这种复杂度为…...

无代码DIY图像检索

软件环境准备 可参见《HuggingFists-低代码玩转LLM RAG-准备篇》中的HuggingFists安装及Milvus安装。 流程环境准备 图片准备 进入HuggingFists内置的文件系统&#xff0c;数据源->文件系统->sengee_fs_settings_201创建Image文件夹将事先准备的多张相同或不同种类的图…...

Elasticsearch--Master选举

角色 主节点&#xff08;active master&#xff09;&#xff1a;一般指的是活跃的主节点&#xff0c;避免负载任务&#xff0c;主节点主要用来管理集群&#xff0c;专用master节点仍将充当协调节点 候选节点&#xff08;master-eligible nodes&#xff09;&#xff1a;默认具备…...

微服务实战系列之Filter

前言 Filter&#xff0c;又名过滤器&#xff0c;当然不是我们日常中见到的&#xff0c;诸如此类构件&#xff1a; 而应该是微服务中常使用的&#xff0c;诸如此类&#xff08;图片来自官网&#xff0c;点击可查看原图&#xff09;&#xff1a; 一般用于字符编码转换&#xf…...

使用GPT大模型调用工具链

本文特指openai使用sdk的方式调用工具链。 安装openai pip install openai export OPENAI_API_KEY"YOUR OPENAI KEY" 定义工具函数 from openai import OpenAI import jsonclient OpenAI() #工具函数 def get_current_weather(location, unit"fahrenheit&q…...

C语言实现bmp图像底层数据写入与创建

要用C语言实现bmp图像底层数据写入进而创建一张bmp图像&#xff0c;需要对bmp图像文件格式非常了解&#xff0c;如果不太熟悉bmp图像文件格式请先移步bmp图像文件格式超详解 创建bmp图像文件的方式有很多&#xff0c;比如用halcon&#xff0c;用qt&#xff0c;这些都是把已经画…...

基于BP神经网络的定位算法,基于BP神经网络定位预测

目录 摘要 BP神经网络参数设置及各种函数选择 参数设置 训练函数 传递函数 学习函数 性能函数 显示函数 前向网络创建函数 BP神经网络训练窗口详解 训练窗口例样 训练窗口四部详解 基于BP神经网络的定位算法,基于BP神经网络定位预测 代码下载:基于BP神经网络的定位算法,基于…...

Java Http各个请求类型详细介绍

1. 前言 在Spring Boot框架中&#xff0c;HTTP请求类型是构建Web应用程序的重要组成部分。常见的请求类型包括GET、POST、PUT和DELETE&#xff0c;每种类型都有其特定的用途和特点。本文将详细比较这四种请求类型&#xff0c;帮助您在开发过程中做出明智的选择。 2. GET请求…...

python函数装饰器参数统计调用时间和次数

1 python函数装饰器参数统计调用时间和次数 python在函数装饰器外层定义一个函数生成封闭作用域来保存装饰器入参&#xff0c;供装饰器使用。 1.1 装饰器统计调用时间和次数 描述 通过类的可调用实例装饰器来统计函数每次调用时间和总调用时间&#xff0c;以及调用次数。 …...

机器学习之集成学习AdaBoost

概念 AdaBoost(Adaptive Boosting)是一种迭代的集成学习算法,其主要目标是通过组合多个弱学习器来创建一个强大的模型。以下是AdaBoost算法的主要步骤: 初始化样本权重: 为每个训练样本分配相等的权重,通常设为 w i = 1 N w_i = \frac{1}{N} w...

行云部署成长之路 -- 慢 SQL 优化之旅 | 京东云技术团队

当项目的SQL查询慢得像蜗牛爬行时&#xff0c;用户的耐心也在一点点被消耗&#xff0c;作为研发&#xff0c;我们可不想看到这样的事。这篇文章将结合行云部署项目的实践经验&#xff0c;带你走进SQL优化的奇妙世界&#xff0c;一起探索如何让那些龟速的查询飞起来&#xff01;…...

Windows权限提升

0x01 简介 提权可分为纵向提权与横向提权&#xff1a; 纵向提权&#xff1a;低权限角色获得高权限角色的权限&#xff1b; 横向提权&#xff1a;获取同级别角色的权限。 Windows常用的提权方法有&#xff1a;系统内核溢出漏洞提权、数据库提权、错误的系统配置提权、组策略首…...

rknn优化教程(二)

文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK&#xff0c;开始写第二篇的内容了。这篇博客主要能写一下&#xff1a; 如何给一些三方库按照xmake方式进行封装&#xff0c;供调用如何按…...

工业安全零事故的智能守护者:一体化AI智能安防平台

前言&#xff1a; 通过AI视觉技术&#xff0c;为船厂提供全面的安全监控解决方案&#xff0c;涵盖交通违规检测、起重机轨道安全、非法入侵检测、盗窃防范、安全规范执行监控等多个方面&#xff0c;能够实现对应负责人反馈机制&#xff0c;并最终实现数据的统计报表。提升船厂…...

安宝特方案丨XRSOP人员作业标准化管理平台:AR智慧点检验收套件

在选煤厂、化工厂、钢铁厂等过程生产型企业&#xff0c;其生产设备的运行效率和非计划停机对工业制造效益有较大影响。 随着企业自动化和智能化建设的推进&#xff0c;需提前预防假检、错检、漏检&#xff0c;推动智慧生产运维系统数据的流动和现场赋能应用。同时&#xff0c;…...

pam_env.so模块配置解析

在PAM&#xff08;Pluggable Authentication Modules&#xff09;配置中&#xff0c; /etc/pam.d/su 文件相关配置含义如下&#xff1a; 配置解析 auth required pam_env.so1. 字段分解 字段值说明模块类型auth认证类模块&#xff0c;负责验证用户身份&am…...

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility 1. 实验室环境1.1 实验室环境1.2 小测试 2. The Endor System2.1 部署应用2.2 检查现有策略 3. Cilium 策略实体3.1 创建 allow-all 网络策略3.2 在 Hubble CLI 中验证网络策略源3.3 …...

最新SpringBoot+SpringCloud+Nacos微服务框架分享

文章目录 前言一、服务规划二、架构核心1.cloud的pom2.gateway的异常handler3.gateway的filter4、admin的pom5、admin的登录核心 三、code-helper分享总结 前言 最近有个活蛮赶的&#xff0c;根据Excel列的需求预估的工时直接打骨折&#xff0c;不要问我为什么&#xff0c;主要…...

在四层代理中还原真实客户端ngx_stream_realip_module

一、模块原理与价值 PROXY Protocol 回溯 第三方负载均衡&#xff08;如 HAProxy、AWS NLB、阿里 SLB&#xff09;发起上游连接时&#xff0c;将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后&#xff0c;ngx_stream_realip_module 从中提取原始信息…...

高等数学(下)题型笔记(八)空间解析几何与向量代数

目录 0 前言 1 向量的点乘 1.1 基本公式 1.2 例题 2 向量的叉乘 2.1 基础知识 2.2 例题 3 空间平面方程 3.1 基础知识 3.2 例题 4 空间直线方程 4.1 基础知识 4.2 例题 5 旋转曲面及其方程 5.1 基础知识 5.2 例题 6 空间曲面的法线与切平面 6.1 基础知识 6.2…...

2025盘古石杯决赛【手机取证】

前言 第三届盘古石杯国际电子数据取证大赛决赛 最后一题没有解出来&#xff0c;实在找不到&#xff0c;希望有大佬教一下我。 还有就会议时间&#xff0c;我感觉不是图片时间&#xff0c;因为在电脑看到是其他时间用老会议系统开的会。 手机取证 1、分析鸿蒙手机检材&#x…...

uniapp中使用aixos 报错

问题&#xff1a; 在uniapp中使用aixos&#xff0c;运行后报如下错误&#xff1a; AxiosError: There is no suitable adapter to dispatch the request since : - adapter xhr is not supported by the environment - adapter http is not available in the build 解决方案&…...