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

第十四届蓝桥杯省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&#xff0c;如果我们砍掉某条边可以让这两个点不连通&#xff0c;那么这条边一定是从 x到 y 路径上的一点&#xff0c;我们可以让从 x到 y 路径的边权值都加1。这个操作我们可以使用树上差分。 对于 …...

windows安装Mysql

一、删除已安装的MySQL服务 1、查找以前是否装有mysql sc query mysql 无结果&#xff0c;说明未安装过mysql或者已经卸载mysql服务&#xff0c;接下来直接安装mysql即可&#xff0c;否则需要删除之前安装的mysql 2、删除mysql 以管理员模式打开命令运行行&#xff0c;运行下…...

Axure大屏可视化模板:多领域数据决策的新引擎

在数据驱动决策的时代&#xff0c;Axure大屏可视化模板凭借交互性与可定制性&#xff0c;成为农业、园区管理、智慧城市、企业及医疗领域的创新工具&#xff0c;助力高效数据展示与智能决策。 核心应用场景 1. 农业精细化&#xff1a;实时监控土壤湿度、作物生长曲线&#x…...

【产品经理从0到1】原型及Axure介绍

原型分类 原型的三种分类&#xff1a; 草图原型&#xff1a;⼿绘稿&#xff0c;制作⽅便&#xff0c;修改不⽅便&#xff1b;低保真原型&#xff1a;简单交互&#xff0c;⽆设计图&#xff1b; 最好的原型是⿊⽩灰的&#xff1b;⾼保真原型&#xff1a;复杂交互&#xff0c;有…...

【激光雷达3D(7)】CenterPoint两阶段细化仅使用BEV特征;PV-RCNN两阶段细化使用体素特征;M3DETRTransformer统一多表征特征

文章目录 1. CenterPoint的两阶段细化模块仅使用鸟瞰视角&#xff08;BEV&#xff09;特征2 PV-RCNN 两阶段3 M3DETR&#xff08;假设为类似DETR的3D检测器&#xff09; 1. CenterPoint的两阶段细化模块仅使用鸟瞰视角&#xff08;BEV&#xff09;特征 CenterPoint的两阶段细化…...

C# 音频分离(MP3伴奏)

编程语言&#xff1a;C# 库&#xff1a;NAudio NAudio 是一个开源的 .NET 音频处理库&#xff0c;它为开发者提供了丰富的功能&#xff0c;能在 Windows 平台上方便地进行音频的录制、播放、处理等操作。以下是关于 NAudio 库的详细介绍&#xff1a; 主要特性 多格式支持&am…...

JavaScript性能优化实战(4):异步编程与主线程优化

JavaScript单线程模型与事件循环深入理解 JavaScript作为一种单线程语言,其执行模型与传统多线程编程语言有着根本性的差异。这种单线程特性既是JavaScript的局限,也是其简洁性的来源。深入理解JavaScript的单线程模型和事件循环机制,对于编写高性能的异步代码至关重要。 …...

Control Center安卓版:自定义控制中心,提升手机操作体验

在使用智能手机的过程中&#xff0c;许多用户希望能够更加便捷地访问常用功能和工具&#xff0c;提升操作效率。今天&#xff0c;我们要介绍的 Control Center安卓版&#xff0c;就是这样一款功能强大的手机控制软件。它不仅提供了简便的操作方法&#xff0c;还允许用户自定义操…...

Web3.0的认知补充(去中心化)

涉及开发技术&#xff1a; Vue Web3.js Solidity 基本认知 Web3.0含义&#xff1a; 新一代互联网思想&#xff1a;去中心化及用户为中心的互联网 数据&#xff1a;可读可写可授权 核心技术&#xff1a;区块链、NFT 应用&#xff1a;互联网上应用 NFT &…...

在Vue3中,如何在父组件中使用v-model与子组件进行双向绑定?

在 Vue 3 里&#xff0c;借助 v-model 可以轻松实现父组件与子组件的双向绑定。以下为你详细介绍实现步骤与示例代码。 实现原理 v-model 在 Vue 3 里是一种语法糖&#xff0c;它本质上是 :modelValue 和 update:modelValue 的组合。父组件借助 :modelValue 向子组件传递数据…...

沁恒MounRiver Studio无法printf浮点数

最近在使用沁恒MounRiver Studio进行CH32V307进行开发&#xff0c;但是遇到了已经成功获得浮点数&#xff0c;但是无法printf输出浮点数 如下图所示&#xff1a; 经过查找资料后&#xff0c;发现沁恒MounRiver Studio如果要printf输出浮点数需要打开Use float with nano print…...

初识Redis · 主从复制(下)

目录 前言&#xff1a; 数据同步 全量复制 部分复制 实时复制 前言&#xff1a; 前文我们已经介绍过了主从复制的基本概念&#xff0c;即分布式系统中存在多个Redis节点&#xff0c;一个是充当为主节点&#xff0c;其他的为从节点&#xff0c;并且从节点也是可以成为主节…...

BDO分厂开展地沟“大清肠”工作

BDO分厂装置区内的地沟主要回收生产过程中产生的污水、日常雨水&#xff0c;日积月累地沟内堆积了一层淤泥和杂物。厚厚的淤泥气味不仅影响员工健康&#xff0c;而且造成排水系统不畅通&#xff0c;存在安全隐患。分厂借助此次待产停车的有利时机对沉积已久的淤泥进行一次彻底“…...

程序和进程的详细对比

&#x1f4a1; 一、程序&#xff08;Program&#xff09; ✅ 定义&#xff1a; 程序是一组指令的集合&#xff0c;通常是一个 可执行文件&#xff08;如 .exe、.out&#xff09;&#xff0c;它是静态的、保存在磁盘上的一段代码&#xff0c;还没有被执行。 ✅ 特点&#xff…...

Flink介绍——实时计算核心论文之Flink论文

引入 通过前面的文章&#xff0c;我们梳理了大数据流计算的核心发展脉络&#xff1a; S4论文详解S4论文总结Storm论文详解Storm论文总结Kafka论文详解Kafka论文总结MillWheel论文详解MillWheel论文总结Dataflow论文详解Dataflow论文总结 而我们专栏的主角Flink正是站在前人的…...

【C++指南】位运算知识详解

. &#x1f493; 博客主页&#xff1a;倔强的石头的CSDN主页 &#x1f4dd;Gitee主页&#xff1a;倔强的石头的gitee主页 ⏩ 文章专栏&#xff1a;《C指南》 期待您的关注 文章目录 引言一、位运算符概述1. 按位与&#xff08;&&#xff09;2. 按位或&#xff08;|&#…...

网络开发基础(游戏)之 数据交换格式

数据交换格式是不同系统、应用程序或组件之间传输和共享数据时使用的标准化数据表示方式。在网络通信中&#xff0c;数据交换格式的选择直接影响系统的性能、可维护性和扩展性。以下是常用的数据交换格式的介绍和选择建议。 Protobuf (Protocol Buffers)协议缓冲区 是 Googl…...

怎么配置一个kubectl客户端访问多个k8s集群

怎么配置一个kubectl客户端访问多个k8s集群 为什么有的客户端用token也访问不了k8s集群&#xff0c;因为有的是把~/.kube/config文件&#xff0c;改为了~/.kube/.config文件&#xff0c;文件设置成隐藏文件了。 按照kubectl的寻找配置的逻辑&#xff0c;kubectl找不到要访问集群…...

【MongoDB】卸载、安装低版本

卸载 MongoDB 的步骤因操作系统而异&#xff0c;以下是 Windows、macOS 和 Linux 的详细卸载方法&#xff1a; 1. Windows 卸载 MongoDB 方法 1&#xff1a;通过控制面板卸载 打开控制面板 Win R → 输入 appwiz.cpl → 回车 找到 MongoDB 在程序列表里找到 MongoDB Server …...

WGAN+U-Net架构实现图像修复

简介 简介:该论文提出了一种基于Wasserstein生成对抗网络(WGAN)的图像修复方法,使用U-Net生成器,通过对抗损失与内容损失联合训练,有效解决了传统方法对破损区域形状大小受限、修复痕迹明显的问题。在CelebA和LFW数据集上的实验表明,该方法修复效果优于现有技术,尤其对…...

vscode vue文件单行注释失效解决办法

打开设置&#xff0c;搜索 files.associations&#xff0c;添加项 *.vue html 点击确定即可...

机器学习(7)——K均值聚类

文章目录 1. K均值&#xff08;K-means&#xff09;聚类是什么算法&#xff1f;2. 核心思想2. 数学目标3. 算法步骤3.1. 选择K个初始质心&#xff1a;3.2.迭代优化3.3. 重复步骤2和步骤3&#xff1a; 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开发者&#xff0c;2025年的技术浪潮将带给我们前所未有的机遇与挑战。本文将带你深入探索Java生态的最新发展&#xff0c;从语言特性到架构革新&#xff0c;助你在技术洪流中把握先机&#xff01; &#x1f31f; 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 磁盘阵列搭建与管理全攻略 在数据存储需求日益增长的今天&#xff0c;磁盘阵列&#xff08;RAID&#xff09;凭借其卓越的性能、数据安全性和可靠性&#xff0c;成为企业级服务器和数据中心的核心存储解决方案。CentOS 7 作为一款稳定且功能强大的 Linux 操作系统&am…...

区块链技术:深入共识算法、智能合约与DApps的架构奥秘

引言&#xff1a;区块链的颠覆性潜力 在数字化浪潮席卷全球的今天&#xff0c;区块链技术以其独特的去中心化特性、不可篡改的数据记录和透明的交易机制&#xff0c;正在重塑我们对信任、价值交换和组织形式的理解。从比特币的诞生到以太坊的智能合约革命&#xff0c;再到如今…...

深度学习物理信息神经网络PINN+大模型辅助编程​

1. 物理信息神经网络&#xff08;PINN&#xff09;的兴起 近年来&#xff0c;物理信息神经网络&#xff08;Physics-Informed Neural Networks, PINN&#xff09;成为计算科学与人工智能交叉领域的前沿方向。传统数值方法&#xff08;如有限差分法、有限单元法&#xff09;在高…...

vue element使用el-table时,切换tab,table表格列项发生错位问题

展示问题 问题描述&#xff1a;使用el-table的fixed"right"属性后&#xff0c;如果切换tab时&#xff0c;回出现最后一列错误的问题 官网提供解决方法&#xff1a;doLayout 需要注意的事项&#xff1a;我这里是通过组件使用的table组件&#xff0c;涉及多层组件封装…...

(八)深入了解AVFoundation-采集:拍照功能的实现

引言 在上一篇文章中&#xff0c;我们初步完成了使用 AVFoundation 采集视频数据的流程&#xff0c;掌握了 AVCaptureSession 的搭建与视频流的预览显示。 本篇将继续深入 AVFoundation&#xff0c;聚焦于静态图片采集的实现。通过 AVCapturePhotoOutput&#xff0c;我们可以…...

C++区别于C语言的提升用法(万字总结)

1.namespace产生原因 在C语言中&#xff0c;变量&#xff0c;函数&#xff0c;以至于类都是大量存在的&#xff0c;因此会产生大量的名称存在于全局作用域中&#xff0c;可能产生很多冲突&#xff0c;至此c的祖师爷为避免命名冲突和名字的污染&#xff0c;造出来了关键字names…...

创新项目实训开发日志4

一、开发简介 核心工作内容&#xff1a;logo实现、注册实现、登录实现、上传gitee 工作时间&#xff1a;第十周 二、logo实现 1.设计logo 2.添加logo const logoUrl new URL(/assets/images/logo.png, import.meta.url).href <div class"aside-first">…...

ospf综合作业

需求 需求分析 区域划分&#xff1a; 网络划分为 area 0、area 1、area 2、area 3、area 4 多个区域。其中 area 0 作为骨干区域&#xff0c;其他为非骨干区域。这种划分符合 OSPF&#xff08;开放式最短路径优先&#xff09;协议中区域设计原则&#xff0c;不同区域通过 ABR…...

旋转磁体产生的场-对导航姿态的影响

pitch、yaw、roll是描述物体在空间中旋转的术语&#xff0c;通常用于计算机图形学或航空航天领域中。这些术语描述了物体绕不同轴旋转的方式&#xff1a; Pitch&#xff08;俯仰&#xff09;&#xff1a;绕横轴旋转&#xff0c;使物体向前或向后倾斜。俯仰角度通常用来描述物体…...

Hive 数据同步到 Doris 最佳实践方案:从场景适配到性能调优全解析

在大数据领域&#xff0c;Hive 作为成熟的数据仓库解决方案&#xff0c;常用于海量数据存储与离线处理&#xff0c;而 Doris 凭借其强大的 OLAP 能力&#xff0c;在实时分析、即席查询等场景表现卓越。当企业需要将 Hive 数据仓库中的数据与 Doris 的分析能力结合时&#xff0c…...

netty中的Channel与Java NIO中的Channel核心对比

Netty的Channel和Java NIO的Channel虽然都用于网络通信,但设计理念、功能扩展及适用场景存在显著差异。以下从核心特性、设计模式及性能优化等维度展开对比: 1. 抽象层次与功能范围 Java NIO Channel 基础IO模型:仅支持非阻塞IO(NIO),如SocketChannel、ServerSocketChann…...

基于whisper和ffmpeg语音转文本小程序

目录 一、环境准备 ✅ 第一步&#xff1a;安装并准备 Conda 环境 ✅ 第二步&#xff1a;创建 Whisper 专用的 Conda 虚拟环境 ✅ 第三步&#xff1a;安装 GPU 加速版 PyTorch&#xff08;适配 RTX 4060&#xff09; ✅ 第四步&#xff1a;安装 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中实现并发编程的重要方式之一&#xff0c;它比线程更轻量级&#xff0c;能够高效处理I/O密集型任务。本文将全面介绍协程的概念、原理、实现方式以及与线程、进程的对比&#xff0c;包含完整的效率对比代码和详细说明&#xff0c;帮助Python开发者深入理解并掌握协…...

服务器部署LLaMAFactory进行LoRA微调

一、什么是LLaMAFactory LlamaFactory 是一个专为 大型语言模型&#xff08;LLM&#xff09;微调 设计的开源工具库&#xff0c;旨在简化大模型&#xff08;如 LLaMA、GPT、Mistral 等&#xff09;的定制化训练流程&#xff0c;降低技术门槛和硬件成本。以下是它的核心功能和应…...

ASP.NET MVC​ 入门指南

以下是一份 MVC&#xff08;Model - View - Controller&#xff09;培训教程&#xff0c;以ASP.NET MVC 为例进行讲解&#xff0c;适合有一定编程基础的学习者快速上手。 1. MVC 概述 1.1 什么是 MVC MVC 是一种软件设计模式&#xff0c;它将应用程序分为三个主要部分&#…...

mapbox高阶,高程影像、行政区边界阴影效果实现

👨‍⚕️ 主页: gis分享者 👨‍⚕️ 感谢各位大佬 点赞👍 收藏⭐ 留言📝 加关注✅! 👨‍⚕️ 收录于专栏:mapbox 从入门到精通 文章目录 一、🍀前言1.1 ☘️mapboxgl.Map 地图对象1.2 ☘️mapboxgl.Map style属性1.3 ☘️line线图层样式1.4 ☘️symbol符号图层…...

如何下载适用于语音识别功能增强的Google Chrome浏览器

谷歌浏览器一直是互联网用户的首选工具之一&#xff0c;尤其是它强大的扩展功能&#xff0c;使得用户可以根据需求定制浏览器。对于需要使用语音识别功能的用户来说&#xff0c;谷歌浏览器提供了优秀的支持&#xff0c;通过简单的设置和插件&#xff0c;可以显著提升语音识别的…...

运维打铁:Centos 7 安装 redis_exporter 1.3.5

文章目录 一、CentOS 7 安装 redis_exporter 1.3.51. 安装2. 配置自启动&#xff0c;并连接 Redis&#xff0c;修改端口3. 配置 Prometheus 采集 redis_exporter 数据4. 配置 Grafana 查看数据5. Redis 集群配置 二、常见问题及解决办法1. 下载二进制包失败2. 解压部署时权限问…...

3台CentOS虚拟机部署 StarRocks 1 FE+ 3 BE集群

背景&#xff1a;公司最近业务数据量上去了&#xff0c;需要做一个漏斗分析功能&#xff0c;实时性要求较高&#xff0c;mysql已经已经不在适用&#xff0c;做了个大数据技术栈选型调研后&#xff0c;决定使用StarRocks StarRocks官网&#xff1a;StarRocks | A High-Performa…...

Oracle 11g RAC ASM磁盘组剔盘、加盘实施过程

环境&#xff1a;AIX6.1 Oracle RAC 11.2.0.3 前期准备&#xff1a; 1.查看DG磁盘组空间情况&#xff1a; –查看DG磁盘组空间情况&#xff1a; ASMCMD> lsdg State Type Rebal Sector Block AU Total_MB Free_MB Req_mir_free_MB Usable_file_MB Of…...

网站高可用架构设计基础——高可用策略和架构原则

一、正面保障与减少损失 要想让系统能够稳定可用&#xff0c;首先要考虑如何避免问题的发生。比如说可以通过 UPS&#xff08;不间断电源&#xff09;来避免服务器断电&#xff0c;可以通过事先增加机器来解决硬件资源不足的问题。 然后&#xff0c;如果问题真的发生了&#…...