当前位置: 首页 > 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;系统内核溢出漏洞提权、数据库提权、错误的系统配置提权、组策略首…...

HBuilderX安装(uni-app和小程序开发)

下载HBuilderX 访问官方网站&#xff1a;https://www.dcloud.io/hbuilderx.html 根据您的操作系统选择合适版本&#xff1a; Windows版&#xff08;推荐下载标准版&#xff09; Windows系统安装步骤 运行安装程序&#xff1a; 双击下载的.exe安装文件 如果出现安全提示&…...

Unsafe Fileupload篇补充-木马的详细教程与木马分享(中国蚁剑方式)

在之前的皮卡丘靶场第九期Unsafe Fileupload篇中我们学习了木马的原理并且学了一个简单的木马文件 本期内容是为了更好的为大家解释木马&#xff08;服务器方面的&#xff09;的原理&#xff0c;连接&#xff0c;以及各种木马及连接工具的分享 文件木马&#xff1a;https://w…...

网站指纹识别

网站指纹识别 网站的最基本组成&#xff1a;服务器&#xff08;操作系统&#xff09;、中间件&#xff08;web容器&#xff09;、脚本语言、数据厍 为什么要了解这些&#xff1f;举个例子&#xff1a;发现了一个文件读取漏洞&#xff0c;我们需要读/etc/passwd&#xff0c;如…...

排序算法总结(C++)

目录 一、稳定性二、排序算法选择、冒泡、插入排序归并排序随机快速排序堆排序基数排序计数排序 三、总结 一、稳定性 排序算法的稳定性是指&#xff1a;同样大小的样本 **&#xff08;同样大小的数据&#xff09;**在排序之后不会改变原始的相对次序。 稳定性对基础类型对象…...

【笔记】WSL 中 Rust 安装与测试完整记录

#工作记录 WSL 中 Rust 安装与测试完整记录 1. 运行环境 系统&#xff1a;Ubuntu 24.04 LTS (WSL2)架构&#xff1a;x86_64 (GNU/Linux)Rust 版本&#xff1a;rustc 1.87.0 (2025-05-09)Cargo 版本&#xff1a;cargo 1.87.0 (2025-05-06) 2. 安装 Rust 2.1 使用 Rust 官方安…...

C/C++ 中附加包含目录、附加库目录与附加依赖项详解

在 C/C 编程的编译和链接过程中&#xff0c;附加包含目录、附加库目录和附加依赖项是三个至关重要的设置&#xff0c;它们相互配合&#xff0c;确保程序能够正确引用外部资源并顺利构建。虽然在学习过程中&#xff0c;这些概念容易让人混淆&#xff0c;但深入理解它们的作用和联…...

C#学习第29天:表达式树(Expression Trees)

目录 什么是表达式树&#xff1f; 核心概念 1.表达式树的构建 2. 表达式树与Lambda表达式 3.解析和访问表达式树 4.动态条件查询 表达式树的优势 1.动态构建查询 2.LINQ 提供程序支持&#xff1a; 3.性能优化 4.元数据处理 5.代码转换和重写 适用场景 代码复杂性…...

逻辑回归暴力训练预测金融欺诈

简述 「使用逻辑回归暴力预测金融欺诈&#xff0c;并不断增加特征维度持续测试」的做法&#xff0c;体现了一种逐步建模与迭代验证的实验思路&#xff0c;在金融欺诈检测中非常有价值&#xff0c;本文作为一篇回顾性记录了早年间公司给某行做反欺诈预测用到的技术和思路。百度…...

群晖NAS如何在虚拟机创建飞牛NAS

套件中心下载安装Virtual Machine Manager 创建虚拟机 配置虚拟机 飞牛官网下载 https://iso.liveupdate.fnnas.com/x86_64/trim/fnos-0.9.2-863.iso 群晖NAS如何在虚拟机创建飞牛NAS - 个人信息分享...

论文阅读笔记——Muffin: Testing Deep Learning Libraries via Neural Architecture Fuzzing

Muffin 论文 现有方法 CRADLE 和 LEMON&#xff0c;依赖模型推理阶段输出进行差分测试&#xff0c;但在训练阶段是不可行的&#xff0c;因为训练阶段直到最后才有固定输出&#xff0c;中间过程是不断变化的。API 库覆盖低&#xff0c;因为各个 API 都是在各种具体场景下使用。…...