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

KubeSphere 容器平台高可用:环境搭建与可视化操作指南

Linux_k8s篇 欢迎来到Linux的世界&#xff0c;看笔记好好学多敲多打&#xff0c;每个人都是大神&#xff01; 题目&#xff1a;KubeSphere 容器平台高可用&#xff1a;环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...

渲染学进阶内容——模型

最近在写模组的时候发现渲染器里面离不开模型的定义,在渲染的第二篇文章中简单的讲解了一下关于模型部分的内容,其实不管是方块还是方块实体,都离不开模型的内容 🧱 一、CubeListBuilder 功能解析 CubeListBuilder 是 Minecraft Java 版模型系统的核心构建器,用于动态创…...

基于Docker Compose部署Java微服务项目

一. 创建根项目 根项目&#xff08;父项目&#xff09;主要用于依赖管理 一些需要注意的点&#xff1a; 打包方式需要为 pom<modules>里需要注册子模块不要引入maven的打包插件&#xff0c;否则打包时会出问题 <?xml version"1.0" encoding"UTF-8…...

《基于Apache Flink的流处理》笔记

思维导图 1-3 章 4-7章 8-11 章 参考资料 源码&#xff1a; https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...

均衡后的SNRSINR

本文主要摘自参考文献中的前两篇&#xff0c;相关文献中经常会出现MIMO检测后的SINR不过一直没有找到相关数学推到过程&#xff0c;其中文献[1]中给出了相关原理在此仅做记录。 1. 系统模型 复信道模型 n t n_t nt​ 根发送天线&#xff0c; n r n_r nr​ 根接收天线的 MIMO 系…...

安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖

在Vuzix M400 AR智能眼镜的助力下&#xff0c;卢森堡罗伯特舒曼医院&#xff08;the Robert Schuman Hospitals, HRS&#xff09;凭借在无菌制剂生产流程中引入增强现实技术&#xff08;AR&#xff09;创新项目&#xff0c;荣获了2024年6月7日由卢森堡医院药剂师协会&#xff0…...

Linux 内存管理实战精讲:核心原理与面试常考点全解析

Linux 内存管理实战精讲&#xff1a;核心原理与面试常考点全解析 Linux 内核内存管理是系统设计中最复杂但也最核心的模块之一。它不仅支撑着虚拟内存机制、物理内存分配、进程隔离与资源复用&#xff0c;还直接决定系统运行的性能与稳定性。无论你是嵌入式开发者、内核调试工…...

Java求职者面试指南:计算机基础与源码原理深度解析

Java求职者面试指南&#xff1a;计算机基础与源码原理深度解析 第一轮提问&#xff1a;基础概念问题 1. 请解释什么是进程和线程的区别&#xff1f; 面试官&#xff1a;进程是程序的一次执行过程&#xff0c;是系统进行资源分配和调度的基本单位&#xff1b;而线程是进程中的…...

用递归算法解锁「子集」问题 —— LeetCode 78题解析

文章目录 一、题目介绍二、递归思路详解&#xff1a;从决策树开始理解三、解法一&#xff1a;二叉决策树 DFS四、解法二&#xff1a;组合式回溯写法&#xff08;推荐&#xff09;五、解法对比 递归算法是编程中一种非常强大且常见的思想&#xff0c;它能够优雅地解决很多复杂的…...

2025年低延迟业务DDoS防护全攻略:高可用架构与实战方案

一、延迟敏感行业面临的DDoS攻击新挑战 2025年&#xff0c;金融交易、实时竞技游戏、工业物联网等低延迟业务成为DDoS攻击的首要目标。攻击呈现三大特征&#xff1a; AI驱动的自适应攻击&#xff1a;攻击流量模拟真实用户行为&#xff0c;差异率低至0.5%&#xff0c;传统规则引…...