洛谷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 认识物理层 物理层目的:解决如何在连接各种计算机的传输媒体上传输数据比特流,而不是具体的传输媒体。 物理层主要任务:确认与传输媒体接口有关的一些特性,需要进行定义标…...
快速构建高质量3D模型的终极指南:Meshroom开源摄影测量工具深度解析
快速构建高质量3D模型的终极指南:Meshroom开源摄影测量工具深度解析 【免费下载链接】Meshroom Node-based Visual Programming Toolbox 项目地址: https://gitcode.com/gh_mirrors/me/Meshroom 你是否曾想过将普通照片变成精美的3D模型?传统的3D…...
OpenCore Legacy Patcher终极指南:3步让老旧Mac重获新生
OpenCore Legacy Patcher终极指南:3步让老旧Mac重获新生 【免费下载链接】OpenCore-Legacy-Patcher Experience macOS just like before 项目地址: https://gitcode.com/GitHub_Trending/op/OpenCore-Legacy-Patcher 你是否拥有一台被苹果官方"抛弃&quo…...
面阵相机 vs 线阵相机:堡盟与大恒相机选型差异全解析 附C++ 实战演示
面阵相机 vs 线阵相机:堡盟与大恒相机选型差异全解析 附C 实战演示面阵 vs 线阵:工业视觉的“广角镜”与“扫描仪”🔍 核心差异:一帧 vs 一行面阵相机 (Area Scan):瞬间的“广角镜”线阵相机 (Line Scan):连…...
芒果叶子病害识别分割数据集labelme格式3642张5类别均为单叶子
注意数据集中大约1/3是原图剩余为增强图片数据集格式:labelme格式(不包含mask文件,仅仅包含jpg图片和对应的json文件)图片数量(jpg文件个数):3642标注数量(json文件个数):3642标注类别数:5标注类别名称:["Anthrac…...
红牌作战的实施方法:详解红牌作战的实施方法与整改流程
红牌作战的实施方法是现代企业现场管理中解决“脏乱差”顽疾的核心手段,它不仅仅是一个简单的贴标签动作,更是一套包含问题识别、责任落实、限期整改到最终验收销号的完整闭环体系。本文将深入拆解红牌作战的实施方法,重点详解如何通过标准化…...
【企业级Dev Container流水线标准】:基于OCI 1.1规范的轻量化镜像构建策略,让团队接入速度提升3.8倍
更多请点击: https://intelliparadigm.com 第一章:VS Code 远程容器开发环境 (Dev Containers) 优化 如何实现快速接入 Dev Containers 是 VS Code 提供的标准化容器化开发方案,通过 .devcontainer/devcontainer.json 定义可复现、即开即用…...
《C盘/D盘满了?别再手动一个个翻文件夹了!用AI自动分析 + 精准清理,释放50G空间》
《C盘/D盘满了?别再手动一个个翻文件夹了!用AI自动分析 精准清理,释放50G空间》 文章目录《C盘/D盘满了?别再手动一个个翻文件夹了!用AI自动分析 精准清理,释放50G空间》先问自己一个问题一、解决问题的思…...
TMSpeech:构建Windows本地实时语音识别系统的完整指南
TMSpeech:构建Windows本地实时语音识别系统的完整指南 【免费下载链接】TMSpeech 腾讯会议摸鱼工具 项目地址: https://gitcode.com/gh_mirrors/tm/TMSpeech TMSpeech是一款基于开源框架的Windows桌面应用,专注于实现完全离线的实时语音转文字功能…...
基于Git提交历史的本地AI代码助手:Machtiani深度解析与实践指南
1. 项目概述:Machtiani,一个能与你的代码库深度对话的本地AI助手 如果你和我一样,每天都要面对一个拥有数千次提交、数万行代码的庞大项目,那么你一定理解那种在代码海洋中寻找特定逻辑或修复一个陈年Bug时的无力感。传统的全局搜…...
AI Agent 三大架构路径:全栈底座、金智维流程执行、Dify 低代码实践
2025年的企业级AI智能体市场,一边是平台数量快速增长,另一边是企业落地节奏明显放缓。原因并不复杂——企业开始从“尝试AI”,转向“要求结果”。当智能体真正进入业务流程,判断标准也变得很直接:能不能稳定执行、能不…...
