第十四届蓝桥杯省B.砍树
第十四届蓝桥杯省B.砍树
题目
题目解析及思路
考虑一对无序数对的点 x和 y,如果我们砍掉某条边可以让这两个点不连通,那么这条边一定是从 x到 y 路径上的一点,我们可以让从 x到 y 路径的边权值都加1。这个操作我们可以使用树上差分。 对于 m个无序数对我们都如此操作,最后如果某条边的权值为 m 则说明它符合条件,我们选出符合条件编号最大的那条边就是答案,如果没有权值为 m的边则说明无解。
树上差分
代码
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define pii pair<int,int>
#define ms(s,x) memset(s, x, sizeof(s))
using namespace std;
typedef pair<int,int> PII;
const int inf = 0x3f3f3f3f;
const int mod = 1000000007;
const int N = 200010;int n, m;
vector<int> e[N];
int depth[N], fa[N][16];
int f[N];
int root;
int ans;
map<PII, int> mp;//lca板子
void bfs(int root){memset(depth,0x3f,sizeof(depth));depth[0] = 0,depth[root] = 1;queue<int> q;q.push(root);while(!q.empty()){int t = q.front();q.pop();for(int j:e[t]){if(depth[j] > depth[t] + 1){depth[j] = depth[t] + 1;q.push(j);fa[j][0] = t;for(int k=1;k<=15;k++){fa[j][k] = fa[fa[j][k-1]][k-1];}}}}
}int lca(int a,int b){if(depth[a] < depth[b]) swap(a,b);for(int k=15;k>=0;k--){if(depth[fa[a][k]] >= depth[b]){a = fa[a][k];}}if(a == b) return a;for(int k=15;k>=0;k--){if(fa[a][k] != fa[b][k]){a = fa[a][k];b = fa[b][k];}}return fa[a][0];
}
//对树上差分数组f进行dfs求和
int dfs(int u,int fa){int res = f[u];for(auto v:e[u]){if(v == fa) continue;int g = dfs(v,u);if(g == m){ans = max(ans,mp[{v,u}]);}res += g;}return res;
}
signed main(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);ans = 0;cin>>n>>m;for(int i=0;i<n-1;i++){int u,v;cin>>u>>v;mp[{u,v}] = mp[{v,u}] = i+1;e[u].push_back(v);e[v].push_back(u);}//lcabfs(1);//树上差分for(int i=0;i<m;i++){int u,v;cin>>u>>v;int z = lca(u,v);f[u] ++;f[v] ++;f[z] -= 2;}dfs(1,-1);cout << (ans == 0 ? -1 : ans) << '\n';
}
相关文章:
第十四届蓝桥杯省B.砍树
第十四届蓝桥杯省B.砍树 题目 题目解析及思路 考虑一对无序数对的点 x和 y,如果我们砍掉某条边可以让这两个点不连通,那么这条边一定是从 x到 y 路径上的一点,我们可以让从 x到 y 路径的边权值都加1。这个操作我们可以使用树上差分。 对于 …...
windows安装Mysql
一、删除已安装的MySQL服务 1、查找以前是否装有mysql sc query mysql 无结果,说明未安装过mysql或者已经卸载mysql服务,接下来直接安装mysql即可,否则需要删除之前安装的mysql 2、删除mysql 以管理员模式打开命令运行行,运行下…...
Axure大屏可视化模板:多领域数据决策的新引擎
在数据驱动决策的时代,Axure大屏可视化模板凭借交互性与可定制性,成为农业、园区管理、智慧城市、企业及医疗领域的创新工具,助力高效数据展示与智能决策。 核心应用场景 1. 农业精细化:实时监控土壤湿度、作物生长曲线&#x…...
【产品经理从0到1】原型及Axure介绍
原型分类 原型的三种分类: 草图原型:⼿绘稿,制作⽅便,修改不⽅便;低保真原型:简单交互,⽆设计图; 最好的原型是⿊⽩灰的;⾼保真原型:复杂交互,有…...
【激光雷达3D(7)】CenterPoint两阶段细化仅使用BEV特征;PV-RCNN两阶段细化使用体素特征;M3DETRTransformer统一多表征特征
文章目录 1. CenterPoint的两阶段细化模块仅使用鸟瞰视角(BEV)特征2 PV-RCNN 两阶段3 M3DETR(假设为类似DETR的3D检测器) 1. CenterPoint的两阶段细化模块仅使用鸟瞰视角(BEV)特征 CenterPoint的两阶段细化…...
C# 音频分离(MP3伴奏)
编程语言:C# 库:NAudio NAudio 是一个开源的 .NET 音频处理库,它为开发者提供了丰富的功能,能在 Windows 平台上方便地进行音频的录制、播放、处理等操作。以下是关于 NAudio 库的详细介绍: 主要特性 多格式支持&am…...
JavaScript性能优化实战(4):异步编程与主线程优化
JavaScript单线程模型与事件循环深入理解 JavaScript作为一种单线程语言,其执行模型与传统多线程编程语言有着根本性的差异。这种单线程特性既是JavaScript的局限,也是其简洁性的来源。深入理解JavaScript的单线程模型和事件循环机制,对于编写高性能的异步代码至关重要。 …...
Control Center安卓版:自定义控制中心,提升手机操作体验
在使用智能手机的过程中,许多用户希望能够更加便捷地访问常用功能和工具,提升操作效率。今天,我们要介绍的 Control Center安卓版,就是这样一款功能强大的手机控制软件。它不仅提供了简便的操作方法,还允许用户自定义操…...
Web3.0的认知补充(去中心化)
涉及开发技术: Vue Web3.js Solidity 基本认知 Web3.0含义: 新一代互联网思想:去中心化及用户为中心的互联网 数据:可读可写可授权 核心技术:区块链、NFT 应用:互联网上应用 NFT &…...
在Vue3中,如何在父组件中使用v-model与子组件进行双向绑定?
在 Vue 3 里,借助 v-model 可以轻松实现父组件与子组件的双向绑定。以下为你详细介绍实现步骤与示例代码。 实现原理 v-model 在 Vue 3 里是一种语法糖,它本质上是 :modelValue 和 update:modelValue 的组合。父组件借助 :modelValue 向子组件传递数据…...
沁恒MounRiver Studio无法printf浮点数
最近在使用沁恒MounRiver Studio进行CH32V307进行开发,但是遇到了已经成功获得浮点数,但是无法printf输出浮点数 如下图所示: 经过查找资料后,发现沁恒MounRiver Studio如果要printf输出浮点数需要打开Use float with nano print…...
初识Redis · 主从复制(下)
目录 前言: 数据同步 全量复制 部分复制 实时复制 前言: 前文我们已经介绍过了主从复制的基本概念,即分布式系统中存在多个Redis节点,一个是充当为主节点,其他的为从节点,并且从节点也是可以成为主节…...
BDO分厂开展地沟“大清肠”工作
BDO分厂装置区内的地沟主要回收生产过程中产生的污水、日常雨水,日积月累地沟内堆积了一层淤泥和杂物。厚厚的淤泥气味不仅影响员工健康,而且造成排水系统不畅通,存在安全隐患。分厂借助此次待产停车的有利时机对沉积已久的淤泥进行一次彻底“…...
程序和进程的详细对比
💡 一、程序(Program) ✅ 定义: 程序是一组指令的集合,通常是一个 可执行文件(如 .exe、.out),它是静态的、保存在磁盘上的一段代码,还没有被执行。 ✅ 特点ÿ…...
Flink介绍——实时计算核心论文之Flink论文
引入 通过前面的文章,我们梳理了大数据流计算的核心发展脉络: S4论文详解S4论文总结Storm论文详解Storm论文总结Kafka论文详解Kafka论文总结MillWheel论文详解MillWheel论文总结Dataflow论文详解Dataflow论文总结 而我们专栏的主角Flink正是站在前人的…...
【C++指南】位运算知识详解
. 💓 博客主页:倔强的石头的CSDN主页 📝Gitee主页:倔强的石头的gitee主页 ⏩ 文章专栏:《C指南》 期待您的关注 文章目录 引言一、位运算符概述1. 按位与(&)2. 按位或(|&#…...
网络开发基础(游戏)之 数据交换格式
数据交换格式是不同系统、应用程序或组件之间传输和共享数据时使用的标准化数据表示方式。在网络通信中,数据交换格式的选择直接影响系统的性能、可维护性和扩展性。以下是常用的数据交换格式的介绍和选择建议。 Protobuf (Protocol Buffers)协议缓冲区 是 Googl…...
怎么配置一个kubectl客户端访问多个k8s集群
怎么配置一个kubectl客户端访问多个k8s集群 为什么有的客户端用token也访问不了k8s集群,因为有的是把~/.kube/config文件,改为了~/.kube/.config文件,文件设置成隐藏文件了。 按照kubectl的寻找配置的逻辑,kubectl找不到要访问集群…...
【MongoDB】卸载、安装低版本
卸载 MongoDB 的步骤因操作系统而异,以下是 Windows、macOS 和 Linux 的详细卸载方法: 1. Windows 卸载 MongoDB 方法 1:通过控制面板卸载 打开控制面板 Win R → 输入 appwiz.cpl → 回车 找到 MongoDB 在程序列表里找到 MongoDB Server …...
WGAN+U-Net架构实现图像修复
简介 简介:该论文提出了一种基于Wasserstein生成对抗网络(WGAN)的图像修复方法,使用U-Net生成器,通过对抗损失与内容损失联合训练,有效解决了传统方法对破损区域形状大小受限、修复痕迹明显的问题。在CelebA和LFW数据集上的实验表明,该方法修复效果优于现有技术,尤其对…...
vscode vue文件单行注释失效解决办法
打开设置,搜索 files.associations,添加项 *.vue html 点击确定即可...
机器学习(7)——K均值聚类
文章目录 1. K均值(K-means)聚类是什么算法?2. 核心思想2. 数学目标3. 算法步骤3.1. 选择K个初始质心:3.2.迭代优化3.3. 重复步骤2和步骤3: 4. 关键参数5. 优缺点6. 改进变种7. K值选择方法8. Python示例9. 应用场景10…...
LainChain技术解析:基于RAG架构的下一代语言模型增强框架
摘要 随着大语言模型(LLM)在自然语言处理领域的突破性进展,如何突破其知识时效性限制、提升事实准确性成为关键挑战。LainChain通过整合检索增强生成(RAG)技术,构建起动态知识接入框架,为LLM提供实时外部知识支持。本文从技术原理、架构设计、应用场景三个维度,深入解…...
Java 使用 RabbitMQ 消息处理(快速上手指南)
目录 一、前言二、RabbitMQ 简介三、开发环境搭建3.1 安装 RabbitMQ在 Ubuntu 上安装在 Windows 上安装使用 Docker 安装3.2 添加 Maven 依赖四、RabbitMQ 的核心概念BrokerVirtual hostConnectionChannelExchangeQueueProducerConsumer五、RabbitMQ 基本操作5.1 发送消息(生产…...
Java 2025 技术全景与实战指南:从新特性到架构革新
作为一名Java开发者,2025年的技术浪潮将带给我们前所未有的机遇与挑战。本文将带你深入探索Java生态的最新发展,从语言特性到架构革新,助你在技术洪流中把握先机! 🌟 Java 2025 新特性全景 1. 模式匹配的全面进化 (J…...
【hadoop】HBase shell 操作
1.创建course表 hbase(main):002:0> create course,cf 2.查看HBase所有表 hbase(main):003:0> list 3.查看course表结构 hbase(main):004:0> describe course 4.向course表插入数据 hbase(main):005:0> put course,001,cf:cname,hbase hbase(main):006:0> …...
rabbitmq死信队列处理
创建私信队列并绑定 # 死信交换机配置 以直连交换机为列 my:exchangeNormalName: exchange.normal.a #正常交换机queueNormalName: queue.normal.a #正常队列exchangeDlxName: exchange.dlx.a #死信交换机queueDlxName: queue.dlx.a #死信队列…...
基于事件驱动的云原生后端架构设计:从理念到落地
📝个人主页🌹:慌ZHANG-CSDN博客 🌹🌹期待您的关注 🌹🌹 一、引言:微服务之后,事件驱动正在成为新范式 随着业务复杂度的提升,传统同步式微服务调用模式逐渐暴露出瓶颈:服务间耦合度高、并发能力有限、出错链路复杂。而在互联网业务、金融交易、物联网等场景中…...
CentOS 7 磁盘阵列搭建与管理全攻略
CentOS 7 磁盘阵列搭建与管理全攻略 在数据存储需求日益增长的今天,磁盘阵列(RAID)凭借其卓越的性能、数据安全性和可靠性,成为企业级服务器和数据中心的核心存储解决方案。CentOS 7 作为一款稳定且功能强大的 Linux 操作系统&am…...
区块链技术:深入共识算法、智能合约与DApps的架构奥秘
引言:区块链的颠覆性潜力 在数字化浪潮席卷全球的今天,区块链技术以其独特的去中心化特性、不可篡改的数据记录和透明的交易机制,正在重塑我们对信任、价值交换和组织形式的理解。从比特币的诞生到以太坊的智能合约革命,再到如今…...
深度学习物理信息神经网络PINN+大模型辅助编程
1. 物理信息神经网络(PINN)的兴起 近年来,物理信息神经网络(Physics-Informed Neural Networks, PINN)成为计算科学与人工智能交叉领域的前沿方向。传统数值方法(如有限差分法、有限单元法)在高…...
vue element使用el-table时,切换tab,table表格列项发生错位问题
展示问题 问题描述:使用el-table的fixed"right"属性后,如果切换tab时,回出现最后一列错误的问题 官网提供解决方法:doLayout 需要注意的事项:我这里是通过组件使用的table组件,涉及多层组件封装…...
(八)深入了解AVFoundation-采集:拍照功能的实现
引言 在上一篇文章中,我们初步完成了使用 AVFoundation 采集视频数据的流程,掌握了 AVCaptureSession 的搭建与视频流的预览显示。 本篇将继续深入 AVFoundation,聚焦于静态图片采集的实现。通过 AVCapturePhotoOutput,我们可以…...
C++区别于C语言的提升用法(万字总结)
1.namespace产生原因 在C语言中,变量,函数,以至于类都是大量存在的,因此会产生大量的名称存在于全局作用域中,可能产生很多冲突,至此c的祖师爷为避免命名冲突和名字的污染,造出来了关键字names…...
创新项目实训开发日志4
一、开发简介 核心工作内容:logo实现、注册实现、登录实现、上传gitee 工作时间:第十周 二、logo实现 1.设计logo 2.添加logo const logoUrl new URL(/assets/images/logo.png, import.meta.url).href <div class"aside-first">…...
ospf综合作业
需求 需求分析 区域划分: 网络划分为 area 0、area 1、area 2、area 3、area 4 多个区域。其中 area 0 作为骨干区域,其他为非骨干区域。这种划分符合 OSPF(开放式最短路径优先)协议中区域设计原则,不同区域通过 ABR…...
旋转磁体产生的场-对导航姿态的影响
pitch、yaw、roll是描述物体在空间中旋转的术语,通常用于计算机图形学或航空航天领域中。这些术语描述了物体绕不同轴旋转的方式: Pitch(俯仰):绕横轴旋转,使物体向前或向后倾斜。俯仰角度通常用来描述物体…...
Hive 数据同步到 Doris 最佳实践方案:从场景适配到性能调优全解析
在大数据领域,Hive 作为成熟的数据仓库解决方案,常用于海量数据存储与离线处理,而 Doris 凭借其强大的 OLAP 能力,在实时分析、即席查询等场景表现卓越。当企业需要将 Hive 数据仓库中的数据与 Doris 的分析能力结合时,…...
netty中的Channel与Java NIO中的Channel核心对比
Netty的Channel和Java NIO的Channel虽然都用于网络通信,但设计理念、功能扩展及适用场景存在显著差异。以下从核心特性、设计模式及性能优化等维度展开对比: 1. 抽象层次与功能范围 Java NIO Channel 基础IO模型:仅支持非阻塞IO(NIO),如SocketChannel、ServerSocketChann…...
基于whisper和ffmpeg语音转文本小程序
目录 一、环境准备 ✅ 第一步:安装并准备 Conda 环境 ✅ 第二步:创建 Whisper 专用的 Conda 虚拟环境 ✅ 第三步:安装 GPU 加速版 PyTorch(适配 RTX 4060) ✅ 第四步:安装 Whisper 和 FFMPEG 依赖 ✅…...
使用ffmpeg 将图片合成为视频,填充模糊背景,并添加两段音乐
1.输入3张图片,每张播放一次,播放两秒,视频分辨率设置为1920:1080,每张图片前0.3秒淡入,后0.3秒淡出,图片宽高比不变,用白色填充空白区域 ffmpeg -loop 1 -t 2 -i "img1.jpg" \-loop 1 -t 2 -i "img2.jpg" \-loop 1 -t 2 -i "img3.jpg" \-filte…...
Python协程详解:从基础到实战
协程是Python中实现并发编程的重要方式之一,它比线程更轻量级,能够高效处理I/O密集型任务。本文将全面介绍协程的概念、原理、实现方式以及与线程、进程的对比,包含完整的效率对比代码和详细说明,帮助Python开发者深入理解并掌握协…...
服务器部署LLaMAFactory进行LoRA微调
一、什么是LLaMAFactory LlamaFactory 是一个专为 大型语言模型(LLM)微调 设计的开源工具库,旨在简化大模型(如 LLaMA、GPT、Mistral 等)的定制化训练流程,降低技术门槛和硬件成本。以下是它的核心功能和应…...
ASP.NET MVC 入门指南
以下是一份 MVC(Model - View - Controller)培训教程,以ASP.NET MVC 为例进行讲解,适合有一定编程基础的学习者快速上手。 1. MVC 概述 1.1 什么是 MVC MVC 是一种软件设计模式,它将应用程序分为三个主要部分&#…...
mapbox高阶,高程影像、行政区边界阴影效果实现
👨⚕️ 主页: gis分享者 👨⚕️ 感谢各位大佬 点赞👍 收藏⭐ 留言📝 加关注✅! 👨⚕️ 收录于专栏:mapbox 从入门到精通 文章目录 一、🍀前言1.1 ☘️mapboxgl.Map 地图对象1.2 ☘️mapboxgl.Map style属性1.3 ☘️line线图层样式1.4 ☘️symbol符号图层…...
如何下载适用于语音识别功能增强的Google Chrome浏览器
谷歌浏览器一直是互联网用户的首选工具之一,尤其是它强大的扩展功能,使得用户可以根据需求定制浏览器。对于需要使用语音识别功能的用户来说,谷歌浏览器提供了优秀的支持,通过简单的设置和插件,可以显著提升语音识别的…...
运维打铁:Centos 7 安装 redis_exporter 1.3.5
文章目录 一、CentOS 7 安装 redis_exporter 1.3.51. 安装2. 配置自启动,并连接 Redis,修改端口3. 配置 Prometheus 采集 redis_exporter 数据4. 配置 Grafana 查看数据5. Redis 集群配置 二、常见问题及解决办法1. 下载二进制包失败2. 解压部署时权限问…...
3台CentOS虚拟机部署 StarRocks 1 FE+ 3 BE集群
背景:公司最近业务数据量上去了,需要做一个漏斗分析功能,实时性要求较高,mysql已经已经不在适用,做了个大数据技术栈选型调研后,决定使用StarRocks StarRocks官网:StarRocks | A High-Performa…...
Oracle 11g RAC ASM磁盘组剔盘、加盘实施过程
环境:AIX6.1 Oracle RAC 11.2.0.3 前期准备: 1.查看DG磁盘组空间情况: –查看DG磁盘组空间情况: ASMCMD> lsdg State Type Rebal Sector Block AU Total_MB Free_MB Req_mir_free_MB Usable_file_MB Of…...
网站高可用架构设计基础——高可用策略和架构原则
一、正面保障与减少损失 要想让系统能够稳定可用,首先要考虑如何避免问题的发生。比如说可以通过 UPS(不间断电源)来避免服务器断电,可以通过事先增加机器来解决硬件资源不足的问题。 然后,如果问题真的发生了&#…...