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

2023NOIP A层联测20-旅行

小 A 旅行到了远方的一座城市,其内部的道路可以被视为一张包含恰好 n n n 个点以及 n n n 条边的无向连通图。这里的居民可以用一种特质的墨水来改变图中某一条边的颜色。

居民们的狂欢节即将开始了,且节日会持续 m m m 天。每一天,居民们会选择图中的一条边,并用某一种颜色的墨水去覆盖这条边原有的颜色。在每一天的最后,他们都想知道当前的城市包含多少个颜色相同的连通块。

特别的,一个颜色相同的连通块指的是一个由一些相同颜色的边组成的连通块。

多组数据 T ≤ 10 T\le10 T10
n , m ≤ 1 0 5 n,m\le10^5 n,m105


首先这个图是基环树。

可以用各种方法求出一开始颜色相同连通块的个数。我使用并查集。

对于每次询问,改变这条边的颜色,贡献只需看两个点的连边情况。

可以分成两部分考虑,先去掉这条边的颜色,再加上修改的颜色。

前一个操作,如果两边都有这种颜色,那么断掉这条边会增加一个连通块;如果两边都没有,就会减少一个;否则不变。

后一个操作,如果两边都有这种颜色,那么断掉这条边会减少一个连通块;如果两边都没有,就会增加一个;否则不变。

但是如果两边的颜色是同一个连通块,那么就不会增加连通块,这种情况只能是环上的边全是一种颜色(在后种情况就是除了当前边全是一种颜色),特判即可。

实现上可以开 n n n 个 map 维护当前点的出边颜色。

时间复杂度 O ( T n log ⁡ n ) O(Tn\log n) O(Tnlogn)

代码如下

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+1;
int n,m,fa[N],bj[N],dfn[N],low[N],num,vis[N],VIS[N];
stack<int> s;
vector<int> ans;
map<int,int> ma[N],ring;
map<pair<int,int>,int> To;
struct Node
{int v,w,id;Node(){}Node(int a,int b,int c){v=a,w=b,id=c;}
};
vector<Node> v[N];
struct node
{int u,v,w;bool operator==(const node &a)const{return u==a.u&&v==a.v&&w==a.w;}
}a[N];
int find(int x)
{return x==fa[x]?x:fa[x]=find(fa[x]);
}
void add(int x,int y)
{int a=find(x),b=find(y);if(a!=b) fa[a]=b;
}
void dfs(int u,int fa)
{dfn[u]=low[u]=++num;s.push(u);for(auto i:v[u]){if(!dfn[i.v]){dfs(i.v,u);low[u]=min(low[u],low[i.v]);if(low[i.v]>=dfn[u]){vector<int> aa;int x=0;do{x=s.top();s.pop();aa.push_back(x);}while(x!=i.v);aa.push_back(u);if(aa.size()>2) ans=aa;}}else if(i.v!=fa) low[u]=min(low[u],dfn[i.v]);}
}
void Dfs(int u,int fa)
{if(VIS[u]) return;VIS[u]=1;for(auto i:v[u]) if(i.v!=fa&&vis[i.v]) ring[i.w]++,Dfs(i.v,u);
}
int main()
{freopen("tour.in","r",stdin);freopen("tour.out","w",stdout);int t;cin>>t;while(t--){memset(VIS,0,sizeof(VIS));memset(vis,0,sizeof(vis));memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));num=0;while(s.size()) s.pop();To.clear();ans.clear();ring.clear();scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) fa[i]=i;for(int i=1,x,y,w;i<=n;i++){scanf("%d%d%d",&a[i].u,&a[i].v,&a[i].w);if(a[i].u>a[i].v) swap(a[i].u,a[i].v);v[a[i].u].push_back(Node(a[i].v,a[i].w,i));v[a[i].v].push_back(Node(a[i].u,a[i].w,i));ma[a[i].u][a[i].w]++;ma[a[i].v][a[i].w]++;To[make_pair(a[i].u,a[i].v)]=i;}dfs(1,0);for(auto i:ans) vis[i]=1;if(ans.size()) for(auto i:v[ans.front()]) if(vis[i.v]){Dfs(ans.front(),i.v);break;}for(int i=1;i<=n;i++){for(auto j:v[a[i].u]){if(j.v==a[i].v) continue;if(j.w==a[i].w) add(i,j.id);}for(auto j:v[a[i].v]){if(j.v==a[i].u) continue;if(j.w==a[i].w) add(i,j.id);}}for(int i=1;i<=n;i++) bj[i]=find(i);sort(bj+1,bj+1+n);int num=unique(bj+1,bj+1+n)-bj-1;for(int i=1,x,y,w;i<=m;i++){scanf("%d%d%d",&x,&y,&w);if(x>y) swap(x,y);int id=To[make_pair(x,y)];int fl1=0,fl2=0;ma[a[id].u][a[id].w]--;ma[a[id].v][a[id].w]--;fl1=ma[a[id].u][a[id].w];fl2=ma[a[id].v][a[id].w];ma[a[id].u][a[id].w]++;ma[a[id].v][a[id].w]++;if(fl1&&fl2&&(!vis[a[id].u]||!vis[a[id].v]||ring.size()>1)) num++;else if(!fl1&&!fl2) num--;ma[a[id].u][a[id].w]--;ma[a[id].v][a[id].w]--;if(vis[a[id].u]&&vis[a[id].v]) ring[a[id].w]--;if(!ring.count(a[id].w)) ring.erase(a[id].w);if(!ma[a[id].u][a[id].w]) ma[a[id].u].erase(a[id].w);if(!ma[a[id].v][a[id].w]) ma[a[id].v].erase(a[id].w);a[id].w=w;ma[a[id].u][a[id].w]++;ma[a[id].v][a[id].w]++;if(vis[a[id].u]&&vis[a[id].v]) ring[a[id].w]++;fl1=0,fl2=0;ma[a[id].u][a[id].w]--;ma[a[id].v][a[id].w]--;fl1=ma[a[id].u][a[id].w];fl2=ma[a[id].v][a[id].w];ma[a[id].u][a[id].w]++;ma[a[id].v][a[id].w]++;if(vis[a[id].u]&&vis[a[id].v]){ring[a[id].w]--;if(!ring.count(a[id].w)) ring.erase(a[id].w);}if(fl1&&fl2&&(!vis[a[id].u]||!vis[a[id].v]||ring.size()>1)) num--;else if(!fl1&&!fl2) num++;if(vis[a[id].u]&&vis[a[id].v]) ring[a[id].w]++;printf("%d\n",num);}for(int i=1;i<=n;i++) v[i].clear(),ma[i].clear();}
}

相关文章:

2023NOIP A层联测20-旅行

小 A 旅行到了远方的一座城市&#xff0c;其内部的道路可以被视为一张包含恰好 n n n 个点以及 n n n 条边的无向连通图。这里的居民可以用一种特质的墨水来改变图中某一条边的颜色。 居民们的狂欢节即将开始了&#xff0c;且节日会持续 m m m 天。每一天&#xff0c;居民们…...

STM32 中断NVIC详解,配置及示例

NVIC全称 Nested Vectored Controller 嵌套向量中断控制器 它是一种硬件设备&#xff0c;用于管理和协调处理器的中断请求。NVIC可以管理多个中断请求&#xff0c;并按优先级处理它们。当一个中断请求到达时&#xff0c;NVIC会确定其优先级并决定是否应该中断当前执行的程序&am…...

10.30英语期中稿

influence of Chinese and Japanese literary culture on the country and the world, and compare the differences between the two 对自己文化影响 中日文学文化比较 表达&#xff0c;餐饮&#xff0c;服装 相似点与不同点 与日本友人交流 draft Chinese and Japanes…...

二维数组如何更快地遍历

二维数组如何更快地遍历 有时候&#xff0c;我们会发现&#xff0c;自己的代码和别人的代码几乎一模一样&#xff0c;但运行时间差了很多&#xff0c;别人是 AC \text{AC} AC&#xff0c;你是 TLE \text{TLE} TLE&#xff0c;这是为什么呢&#xff1f; 一个可能的原因是数组的…...

【网络安全】Seeker内网穿透追踪定位

Seeker追踪定位对方精确位置 前言一、kali安装二、seeker定位1、ngrok平台注册2、获取一次性邮箱地址3、ngrok平台登录4、ngrok下载5、ngrok令牌授权6、seeker下载7、运行seeker定位8、运行隧道开启监听9、伪装链接10、用户点击&#xff08;获取定位成功&#xff09;11、利用经…...

Spring Boot 3系列之一(初始化项目)

近期&#xff0c;JDK 21正式发布&#xff0c;而Spring Boot 3也推出已有一段时间。作为这两大技术领域的新一代标杆&#xff0c;它们带来了许多令人振奋的新功能和改进。尽管已有不少博客和文章对此进行了介绍&#xff0c;但对于我们这些身处一线的开发人员来说&#xff0c;有些…...

用python判断一个数是否为素数

判断一个数是否为素数可以使用以下方法&#xff1a; 排除特殊情况&#xff1a;首先判断该数是否小于等于1&#xff0c;因为素数定义中&#xff0c;素数必须大于1。如果小于等于1&#xff0c;则该数不是素数。 除尽法&#xff08;试除法&#xff09;&#xff1a;从2开始&#x…...

FreeRTOS_信号量之二值信号量

目录 1. 信号量简介 2. 二值信号量 2.1 二值信号量简介 2.1.1 二值信号量无效 2.1.2 中断释放信号量 2.1.3 任务获取信号量成功 2.1.4 任务再次进入阻塞态 2.2 创建二值信号量 2.2.1 vSemaphoreCreateBinary() 2.2.2 xSemaphoreCreateBinary() 2.2.3 xSemaphoreCrea…...

使用Gateway解决跨域问题时配置文件不生效的情况之一

首先html文件只有一个发送ajax请求 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta http-equiv"X-UA-Compatible" content"IEedge"><meta name"viewport" content&q…...

【火影手游】新版押镖护送高分攻略

文章目录 Part.I IntroductionPart.II 迪达拉视角1、打栅栏2、石头边&#xff0c;打石头和栅栏3、石头边&#xff0c;踩封印&#xff0c;撞力士4、大树前&#xff0c;打石头和栅栏5、石头边&#xff0c;给佩恩当路标6、后一前二接大招7、补伤害 Part.III 佩恩视角1、头进洞&…...

【JVM】类的声明周期(加载、连接、初始化)

&#x1f40c;个人主页&#xff1a; &#x1f40c; 叶落闲庭 &#x1f4a8;我的专栏&#xff1a;&#x1f4a8; c语言 数据结构 javaEE 操作系统 Redis 石可破也&#xff0c;而不可夺坚&#xff1b;丹可磨也&#xff0c;而不可夺赤。 JVM 一、类的声明周期&#xff08;加载阶段…...

开源3D激光(视觉)SLAM算法汇总(持续更新)

原文连接 目录 一、Cartographer 二、hdl_graph_slam 三、LOAM 四、LeGO-LOAM 五、LIO-SAM 六、S-LOAM 七、M-LOAM 八、livox-loam 九、Livox-Mapping 十、LIO-Livox 十一、FAST-LIO2 十二、LVI-SAM 十三、FAST-Livo 十四、R3LIVE 十五、ImMesh 十六、Point-LIO 一、Cartograph…...

绕WAF手法总结

云锁 被拦截 http://www.test123.com/article.php?id1%20union%20select%201,2,3 绕过 http://www.test123.com/article.php?id-1/*!36000union*//*!36000distinct*//*!36000select*/1,2,user() 360websec 被拦截 http://www.xxx.com.cn/productshow.php?id79 绕过 http:/…...

Linux mv命令:移动文件或改名

mv 命令&#xff08;move 的缩写&#xff09;&#xff0c;既可以在不同的目录之间移动文件或目录&#xff0c;也可以对文件和目录进行重命名。该命令的基本格式如下&#xff1a; [rootlocalhost ~]# mv 【选项】 源文件 目标文件 -f&#xff1a;强制覆盖&#xff0c;如果目标文…...

在 Elasticsearch 中丰富你的 Elasticsearch 文档

作者&#xff1a;David Pilato 对于 Elasticsearch&#xff0c;我们知道联接应该在 “索引时” 而不是查询时完成。 本博文是一系列三篇博文的开始&#xff0c;因为我们可以在 Elastic 生态系统中采取多种方法。 我们将介绍如何在 Elasticsearch 中做到这一点。 下一篇博文将介…...

探营云栖大会:蚂蚁集团展出数字人全栈技术,三大AI“机器人”引关注

一年一度的科技盛会云栖大会将于10月31日正式开幕。30日&#xff0c;记者来到云栖大会展区探营&#xff0c;提前打卡今年上新的“黑科技”。 记者在蚂蚁集团展馆看到&#xff0c;超1亿人参与的亚运“数字火炬手”全栈技术首次公开展示&#xff0c;还可体验基于数字人技术的“数…...

hdlbits系列verilog解答(8位宽移位寄存器)-24

文章目录 一、问题描述二、verilog源码三、仿真结果一、问题描述 这项练习是module_shift移位寄存器的延伸。模块端口不是只有单个引脚,我们现在有以向量作为端口的模块,您将在其上附加线向量而不是普通线网数据。与 Verilog 中的其他位置一样,端口的向量长度不必与连接到它…...

LeetCode 275. H 指数 II

原题链接&#xff1a;力扣&#xff08;LeetCode&#xff09;官网 - 全球极客挚爱的技术成长平台 题目描述 给你一个整数数组 citations &#xff0c;其中 citations[i] 表示研究者的第 i 篇论文被引用的次数&#xff0c;citations 已经按照 升序排列 。计算并返回该研究者的 h…...

Android 优质的UI组件汇总

1、RuleView &#xff1a;Android自定义标尺控件(选择身高、体重等) 链接&#xff1a;https://github.com/cStor-cDeep/RuleView 2、DashboardView &#xff1a;Android自定义仪表盘View&#xff0c;仿新旧两版芝麻信用分、炫酷汽车速度仪表盘 链接&#xff1a;https://git…...

halcon roberts、 prewitt_amp、 sobel_amp、 edges_image、 laplace_of_gauss 对比

原图 灰度&#xff1a; roberts 算子&#xff1a; prewitt算子 sobel 算子 canny算子 拉普拉斯 代码&#xff1a; read_image (Image, C:/Users/alber/Desktop/opencv_images/canny.png) rgb1_to_gray (Image, GrayImage)* 测试 roberts 算子 roberts (GrayImage, ImageRoberts…...

Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)

文章目录 1.什么是Redis&#xff1f;2.为什么要使用redis作为mysql的缓存&#xff1f;3.什么是缓存雪崩、缓存穿透、缓存击穿&#xff1f;3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...

【JVM】- 内存结构

引言 JVM&#xff1a;Java Virtual Machine 定义&#xff1a;Java虚拟机&#xff0c;Java二进制字节码的运行环境好处&#xff1a; 一次编写&#xff0c;到处运行自动内存管理&#xff0c;垃圾回收的功能数组下标越界检查&#xff08;会抛异常&#xff0c;不会覆盖到其他代码…...

将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?

Otsu 是一种自动阈值化方法&#xff0c;用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理&#xff0c;能够自动确定一个阈值&#xff0c;将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...

ffmpeg(四):滤镜命令

FFmpeg 的滤镜命令是用于音视频处理中的强大工具&#xff0c;可以完成剪裁、缩放、加水印、调色、合成、旋转、模糊、叠加字幕等复杂的操作。其核心语法格式一般如下&#xff1a; ffmpeg -i input.mp4 -vf "滤镜参数" output.mp4或者带音频滤镜&#xff1a; ffmpeg…...

【论文笔记】若干矿井粉尘检测算法概述

总的来说&#xff0c;传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度&#xff0c;通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...

ETLCloud可能遇到的问题有哪些?常见坑位解析

数据集成平台ETLCloud&#xff0c;主要用于支持数据的抽取&#xff08;Extract&#xff09;、转换&#xff08;Transform&#xff09;和加载&#xff08;Load&#xff09;过程。提供了一个简洁直观的界面&#xff0c;以便用户可以在不同的数据源之间轻松地进行数据迁移和转换。…...

鱼香ros docker配置镜像报错:https://registry-1.docker.io/v2/

使用鱼香ros一件安装docker时的https://registry-1.docker.io/v2/问题 一键安装指令 wget http://fishros.com/install -O fishros && . fishros出现问题&#xff1a;docker pull 失败 网络不同&#xff0c;需要使用镜像源 按照如下步骤操作 sudo vi /etc/docker/dae…...

k8s业务程序联调工具-KtConnect

概述 原理 工具作用是建立了一个从本地到集群的单向VPN&#xff0c;根据VPN原理&#xff0c;打通两个内网必然需要借助一个公共中继节点&#xff0c;ktconnect工具巧妙的利用k8s原生的portforward能力&#xff0c;简化了建立连接的过程&#xff0c;apiserver间接起到了中继节…...

代理篇12|深入理解 Vite中的Proxy接口代理配置

在前端开发中,常常会遇到 跨域请求接口 的情况。为了解决这个问题,Vite 和 Webpack 都提供了 proxy 代理功能,用于将本地开发请求转发到后端服务器。 什么是代理(proxy)? 代理是在开发过程中,前端项目通过开发服务器,将指定的请求“转发”到真实的后端服务器,从而绕…...

Springboot社区养老保险系统小程序

一、前言 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;社区养老保险系统小程序被用户普遍使用&#xff0c;为方…...