洛谷P4185 离线+并查集

好题,发现没有强制在线,可以离线操作
排序之后带集合点数的并查集就好了
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int n,m;
int p[N],sz[N];int find(int x){if(x!=p[x])p[x] = find(p[x]);return p[x];
}
struct Node{int k,v,id;bool operator<(const Node&W)const{return k>W.k;}
}query[N];
struct Edge{int p,q,r;bool operator<(const Edge&Ws)const{return r>Ws.r;}
}edge[N];
vector<int>ans(100020,0);
int main()
{cin>>n>>m;for(int i=1;i<=n;i++)p[i] = i,sz[i] = 1;for(int i=1;i<=n-1;i++){int p,q,r;cin>>p>>q>>r;edge[i] = {p,q,r};}for(int i=1;i<=m;i++){int k,v;cin>>k>>v;query[i] = {k,v,i};}sort(edge+1,edge+1+n-1);sort(query+1,query+1+m);for(int i=1,j=0;i<=m;i++){int ks = query[i].k;while(j+1<=n&&edge[j+1].r>=ks){++j;int a = find(edge[j].p),b = find(edge[j].q);if(a!=b){sz[b]+=sz[a];p[a] = b;}}ans[query[i].id] = sz[find(query[i].v)]-1;}for(int i=1;i<=m;i++)cout<<ans[i]<<"\n";
}
相关文章:
洛谷P4185 离线+并查集
好题,发现没有强制在线,可以离线操作 排序之后带集合点数的并查集就好了 #include<bits/stdc.h> using namespace std; const int N 1e510; int n,m; int p[N],sz[N];int find(int x){if(x!p[x])p[x] find(p[x]);return p[x]; } struct Node{in…...
遇到java.security.AccessControlException:access denied怎么办?
今天工作中遇到了如下报错,记录一下解决方案。 目录 问题 分析 结论 问题 这个问题出现在openjdk8启动网页端Java应用。 Java Exception:java.security.AccessControlException:access denied("java.net.SocketPermission""22.188.130.11:9000…...
c++对接CAT1400
最近工作中遇到需要对接1400协议,网上搜索不到c/c++的实现,所以记录一下自己的实现。 第一步注册: 1400是在http摘要认证的基础上做的,所以要去了解http摘要认证的流程 说明: 1.视图库通过用户分配,手动分配username,password给三方对接程序 2.三方对接程序第一次请求由…...
Linux基础【Linux知识贩卖机】
偶尔的停顿和修整,对于人生是非常必要的。 --随记 文章目录 Linux目录目录结构磁盘分区相关命令 相对路径和绝对路径 文件权限用户分类umask创建文件权限计算方法粘滞位 总结 Linux目录 目录结构 Linux 操作系统采用了一种层次化的目录结构,常被称为标…...
CSS 边框、轮廓线
一、CSS边框: CSS边框属性允许指定一个元素边框的样式和颜色。 1)、边框样式:border-style属性用来定义边框的样式,border-style值: 2)、边框宽度:border-width属性用于指定边框宽度。指定变宽…...
Transformer架构 完整的处理流程
Transformer 是由多层的 Encoder 和 Decoder 构成的。每一层的 Encoder 和 Decoder 都包含了多头自注意力机制(Multi-head Self Attention)、前馈神经网络(Feed Forward)和添加及归一化(Add & Norm)。特…...
git and svn 行尾风格配置强制为lf
git CLI配置: // 提交时转换为LF,检出时转换为CRLF git config --global core.autocrlf true // 提交时转换为LF,检出时不转换 git config --global core.autocrlf input // 提交检出均不转换 git config --global core.autocrlf f…...
达梦数据库答案
1、 创建数据库实例,到/dm8/data下,数据库名:DEMO,实例名DEMOSERVER(10分) [dmdbadmServer ~]$ cd /dm8/tool [dmdbadmServer tool]$ ./dbca.sh1、 簇大小32,页大小16,登录密码&…...
基于SSM的楼房销售系统设计与实现
末尾获取源码 开发语言:Java Java开发工具:JDK1.8 后端框架:SSM 前端:采用JSP技术开发 数据库:MySQL5.7和Navicat管理工具结合 服务器:Tomcat8.5 开发软件:IDEA / Eclipse 是否Maven项目&#x…...
Blender做一个小凳子学习笔记
文章目录 创建椅座椅子腿靠背渲染 本文是这个B站视频的学习笔记:【Blender】爆肝两个月!拜托三连了!这绝对是全B站最用心的(没有之一)Blender 3D建模零基础入门 创建椅座 首先,需要了解其左上角和右上角的…...
Maven简介
一、Maven模型 二、模型实现 三、对应代码项目介绍...
后端工程化 | SpringBoot 知识点
文章目录 [SpringBoot] 后端工程化1 需求2 开发流程3 RequestController 类(操作类)3.1 简单参数(形参名和请求参数名一致)3.2 简单参数(形参名和请求参数名不一致)3.3 复杂实体参数3.4 数组参数3.5 集合参…...
Oracle(15)Managing Users
目录 一、基础知识 1、Users and Security 用户和安全 2、Database Schema 3、Checklist for Creating Users创建用户步骤 二、基础操作 1、创建一个用户 2、OS Authentication 操作系统身份验证 3、Dropping a User 删除用户 4、Getting User Information 获取用户信…...
自动化测试(Java+eclipse)教程
webdriver环境配置 1.下载chromedriver到本地(一定要选择和自己浏览器相对应的版本chromedriver下载地址) 2.加入到环境变量path中 webdriver工作原理 创建web自动化测试脚本 1.Maven项目创建 File->New->project->(搜索maven)选择maven pr…...
ThreadFactory 实例创建方式
匿名内部类 private final Executor executor;{ThreadFactory threadFactory new ThreadFactory() {Overridepublic Thread newThread(Runnable r) {Thread t new Thread(r);t.setDaemon(true);return t;}};executor Executors.newFixedThreadPool(shops.size(), threadFac…...
【自动化测试】Pytest框架 —— 跳过测试和失败重试
1、Pytest跳过测试用例 自动化测试执行过程中,我们常常出现这种情况:因为功能阻塞,未实现或者环境有问题等等原因,一些用例执行不了, 如果我们注释掉或删除掉这些测试用例,后面可能还要进行恢复操作&#…...
python 时间加法 输出t分钟后的时间
题目: 现在时间是a点b分,请问t分钟后,是几点几分? 输入: 第一行包含一个整数a 第二行包含一个整数b 第三行包含一个整数t 其中,0≤a≤23,0≤b≤59,0≤t,t分钟后还…...
51单片机-串口通信
文章目录 前言1.基础介绍2.串口实战3.4. 前言 1.基础介绍 常见1,2,3,电源 常用方式1 fosc外部晶振 2.串口实战 3. 4....
JAVA微信端医院3D智能导诊系统源码
医院智能导诊系统利用高科技的信息化手段,优化就医流程。让广大患者有序、轻松就医,提升医疗服务水平。 随着人工智能技术的快速发展,语音识别与自然语言理解技术的成熟应用,基于人工智能的智能导诊导医逐渐出现在患者的生活视角中…...
考研408-计算机网络 第二章-物理层学习笔记及习题
第二章 物理层 一 通信基础 1.1 物理层基本概念 1.1.1 认识物理层 物理层目的:解决如何在连接各种计算机的传输媒体上传输数据比特流,而不是具体的传输媒体。 物理层主要任务:确认与传输媒体接口有关的一些特性,需要进行定义标…...
别再自己画验证码了!Vue3项目里用这个npm包5分钟搞定滑动拼图(附Element Plus适配)
Vue3Element Plus项目中5分钟集成滑动拼图验证码的终极指南 在快节奏的前端开发中,验证码功能是保护系统安全的基础防线,但自行开发往往耗时费力。本文将带你绕过Canvas绘制的技术深坑,直接使用vue3-puzzle-vcode这个专为Vue3设计的验证码组…...
紧急预警:MCP 2026 V2.1草案已冻结,2025年1月起全面启用新诊断协议(UDS over CAN FD),现有ECU固件兼容率不足41%
更多请点击: https://intelliparadigm.com 第一章:MCP 2026农业设备数据对接的演进逻辑与战略紧迫性 农业智能化正从单点自动化迈向全域协同决策,而MCP(Machine Communication Protocol)2026标准的落地,已…...
如何快速诊断GPU内存故障:MemtestCL完整指南
如何快速诊断GPU内存故障:MemtestCL完整指南 【免费下载链接】memtestCL OpenCL memory tester for GPUs 项目地址: https://gitcode.com/gh_mirrors/me/memtestCL 还在为显卡频繁崩溃而烦恼吗?每次运行大型游戏或专业软件时,系统突然…...
GAN技术发展与应用:从基础到前沿
1. 生成对抗网络(GAN)技术发展概述生成对抗网络(Generative Adversarial Networks)自2014年由Ian Goodfellow等人提出以来,已成为人工智能领域最具革命性的技术之一。这项技术的核心创新在于通过两个神经网络——生成器…...
【国家级农机数据治理白皮书首发】:基于23省217台智能拖拉机实测数据,提炼MCP 2026对接成功率提升62%的4步标准化流程
更多请点击: https://intelliparadigm.com 第一章:MCP 2026农业设备数据对接的国家战略意义与白皮书发布背景 国家粮食安全与数字农业协同升级的关键支点 MCP(Multi-Connect Protocol)2026标准是我国首个面向智能农机全生命周期…...
2026年论文摘要和引言AI率偏高攻略:开篇内容降AI完整处理方案
2026年论文摘要和引言AI率偏高攻略:开篇内容降AI完整处理方案 从AI率73%到6%,我花了不到一个晚上。论文摘要降AI完整经历记录。 核心工具:嘎嘎降AI(www.aigcleaner.com),4.8元,达标率99.26%。…...
终极指南:Agent创业机会,从垂直领域切入
终极指南:Agent创业机会,从垂直领域切入 引言 痛点引入:AI Agent浪潮下,普通创业者/技术人该怎么抢滩? 过去两年的AI技术发展,完全是“天翻地覆”级别的——ChatGPT的诞生把通用大语言模型(LLM&…...
GPT-Image-2刚出圈,国产AI生图就“硬刚“成功!
这两天,朋友圈被美国AI模型GPT-Image-2刷屏了。这款模型在文字渲染、信息图生成、复杂UI布局等方面表现惊艳,甚至让人直呼"设计师要失业"。然而,就在全网热议之际,一家低调的国产公司突然甩出一张"王炸"——兔…...
如何快速获取中兴光猫完整权限:新手友好的终极指南
如何快速获取中兴光猫完整权限:新手友好的终极指南 【免费下载链接】zteOnu A tool that can open ZTE onu device factory mode 项目地址: https://gitcode.com/gh_mirrors/zt/zteOnu 你是否曾因中兴光猫的管理限制而感到困扰?想调整网络参数却找…...
基于Git提交历史的本地AI代码助手:Machtiani深度解析与实践指南
1. 项目概述:Machtiani,一个能与你的代码库深度对话的本地AI助手 如果你和我一样,每天都要面对一个拥有数千次提交、数万行代码的庞大项目,那么你一定理解那种在代码海洋中寻找特定逻辑或修复一个陈年Bug时的无力感。传统的全局搜…...
