第十四届蓝桥杯大赛软件赛省赛 C/C++ 大学 A 组 E 题
颜色平衡树
- ==问题描述==
- ==格式输入==
- ==格式输出==
- ==样例输入==
- ==样例输出==
- ==评测用例规模与约定==
- ==解析==
- ==参考程序==
问题描述


格式输入
输入的第一行包含一个整数 n ,表示树的结点数。
接下来 n 行,每行包含两个整数 Ci
, Fi,用一个空格分隔,表示第 i 个结点
的颜色和父亲结点编号。
特别地,输入数据保证 F1 为 0 ,也即 1 号点没有父亲结点。保证输入数
据是一棵树。
格式输出
输出一行包含一个整数表示答案。
样例输入
6
2 0
2 1
1 2
3 3
3 4
1 4
样例输出
4 编号为 1, 3, 5, 6 的 4 个结点对应的子树为颜色平衡树。
评测用例规模与约定
对于 30% 的评测用例,n ≤ 200,Ci ≤ 200 ;
对于 60% 的评测用例,n ≤ 5000,Ci ≤ 5000 ;
对于所有评测用例,1 ≤ n ≤ 200000,1 ≤ Ci ≤ 200000,0 ≤ Fi < i 。
解析
十四届蓝桥
参考程序
#include<bits/stdc++.h>
using namespace std;
const int N = 200000 + 7;
int col[N], f, n, ans;
struct node {int to, next;
}edge[N];
int head[N], cnt, num[N];
inline void add(int x, int to) {edge[++cnt].to = to;edge[cnt].next = head[x];head[x] = cnt;
}
int dfn, in[N], out[N], belong[N], newcol[N];
unordered_map<int, int> mp;
inline void dfs(int x) {in[x] = ++dfn;for (int i = head[x]; i; i = edge[i].next) {int y = edge[i].to;dfs(y);}out[x] = dfn;
}
struct mo {int l, r;
}q[N << 1];
inline bool cmp(const mo& a, const mo& b) {return belong[a.l] == belong[b.l] ? a.r < b.r : a.l < b.l;
}
inline void del(int x) {int c = newcol[x];mp[num[c]]--;if (mp[num[c]] == 0) {mp.erase(num[c]);}num[c]--;if (num[c]) mp[num[c]]++;
}
inline void add(int x) {int c = newcol[x];if (num[c]) mp[num[c]]--;if (mp[num[c]] == 0) {mp.erase(num[c]);}num[c]++;mp[num[c]]++;
}
inline void Case_Test() {cin >> n;for (int i = 1; i <= n; i++) {cin >> col[i] >> f;if (f) add(f, i);}dfs(1);for (int i = 1; i <= n; i++) {// cout << i << " : [" << in[i] << "," << out[i] << "]" << endl;q[i].l = in[i], q[i].r = out[i];newcol[in[i]] = col[i]; newcol[out[i]] = col[i];// dfn改变原来位置,需要用newcol}int sq = sqrt(dfn);// 根号for (int i = 1; i <= dfn; i++) {belong[i] = (i - 1) / sq + 1;// 预处理}sort(q + 1, q + 1 + n, cmp);// 查询区间排序int l = 1, r = 0;// 莫队初始化for (int i = 1; i <= n; i++) {while (l < q[i].l) del(l++);while (l > q[i].l) add(--l);while (r < q[i].r) add(++r);while (r > q[i].r) del(r--);// 莫队四种转移if (mp.size() == 1) ans++;}cout << ans;
}
int main()
{Case_Test();return 0;
}
以个人刷题整理为目的,如若侵权,请联系删除~
相关文章:
第十四届蓝桥杯大赛软件赛省赛 C/C++ 大学 A 组 E 题
颜色平衡树问题描述格式输入格式输出样例输入样例输出评测用例规模与约定解析参考程序问题描述 格式输入 输入的第一行包含一个整数 n ,表示树的结点数。 接下来 n 行,每行包含两个整数 Ci , Fi,用一个空格分隔,表示第 i 个结点 …...
Python 小型项目大全 21~25
二十一、DNA 可视化 原文:http://inventwithpython.com/bigbookpython/project21.html 脱氧核糖核酸是一种微小的分子,存在于我们身体的每个细胞中,包含着我们身体如何生长的蓝图。它看起来像一对核苷酸分子的双螺旋结构:鸟嘌呤、…...
MinIO从信息泄漏到RCE
文章目录信息泄露漏洞利用漏洞分析漏洞修复RCE漏洞分析参考文章信息泄露 漏洞利用 如果MinIO以集群方式部署,存在信息泄露漏洞,攻击者可以通过HTTP请求获取目标进程的所有环境变量,包括MINIO_SECRET_KEY和MINIO_ROOT_PASSWORD. vulhub有环…...
202.Spark(九):SparkStreaming案例实操
目录 一、启动zookeeper,kafka基础环境 二、项目导好jar包,并且创建源数据,并在kafka中测试能否消费到数据...
GlusterFS(GFS)分布式文件系统
目录 一.文件系统简介 1.文件系统的组成 2.文件系统的作用 3.文件系统的挂载使用 二.GlusterFS概述 1.GlusterFS是什么? 2.GlusterFS的特点 3.GlusterFS术语介绍 3.1 Brick(存储块) 3.2 Volume(逻辑卷) 3.3…...
ChatGPT文本框再次升级,打造出新型操作系统
在ChatGPT到来之前,没有谁能够预见。但是,它最终还是来了,并引起了不小的轰动,甚至有可能颠覆整个行业。 从某种程度上说,ChatGPT可能是历史上增长最快的应用程序,仅在两个多月就拥有了1亿多活跃用户&…...
DPU02国产USB转UART控制芯片替代CP2102
目录DPU02简介DPU02芯片特性应用DPU02简介 DPU02是高度集成的USB转UART的桥接控制芯片,该芯片为RS-232设计更新为USB设计,并简化PCB组件空间提供了一个简单的解决方案。 DPU02包括了一个USB 2.0全速功能控制器、USB收发器、振荡器、EEPROM和带…...
Softing新版HART多路复用器软件支持西门子控制器
用于访问配置和诊断数据的HART多路复用器软件——Softing smartLink SW-HT,现在支持西门子的ET200远程IO和FDT/DTM接口。 smartLink SW-HT是一个基于Docker容器的软件应用。通过该软件,用户可以快速地访问以太网远程IO的HART设备,并且无需额外…...
〖Python网络爬虫实战⑫〗- XPATH语法介绍
订阅:新手可以订阅我的其他专栏。免费阶段订阅量1000python项目实战 Python编程基础教程系列(零基础小白搬砖逆袭) 说明:本专栏持续更新中,目前专栏免费订阅,在转为付费专栏前订阅本专栏的,可以免费订阅付费…...
实例方法、类方法、静态方法、实例属性、类属性
背景:今天在复习类相关知识的时候,突然想到这几种类型的方法的区别和用法,感觉有点模棱两可,于是总结一下,加深记忆。 定义:想要区别和理解几种方法,首先要定义一个类,要在类中加深…...
数据结构---二叉树
专栏:数据结构 个人主页:HaiFan. 专栏简介:这里是HaiFan.的数据结构专栏,今天的内容是二叉树。 二叉树树的概念及结构二叉树概念及结构二叉树的概念二叉树的存储结构二叉树的顺序结构及实现大根堆和小根堆堆的实现及其各个接口堆的…...
CMake——从入门到百公里加速6.7s
目录 一、前言 二、HelloWorld 三、CMAKE 界面 3.1 gui正则表达式 3.2 GUI构建 四 关键字 4.1 add_library 4.2 add_subdirectory 4.3 add_executable 4.4 aux_source_directory 4.5 SET设置变量 4.6 INSTALL安装 4.7 ADD_LIBRARY 4.8 SET_TARGET_PROPERTIES 4.9…...
无公网IP,在外公网远程访问RabbitMQ服务「内网穿透」
文章目录前言1.安装erlang 语言2.安装rabbitMQ3. 内网穿透3.1 安装cpolar内网穿透(支持一键自动安装脚本)3.2 创建HTTP隧道4. 公网远程连接5.固定公网TCP地址5.1 保留一个固定的公网TCP端口地址5.2 配置固定公网TCP端口地址前言 RabbitMQ是一个在 AMQP(高级消息队列协议)基础上…...
Node【二】NPM
文章目录🌟前言🌟NPM使用🌟NPM使用场景🌟NPM的常用命令🌟NPM命令使用介绍🌟 使用NPM安装模块🌟 下载三方包🌟 全局安装VS本地安装🌟 本地安装🌟 全局安装&…...
【2023最新】超详细图文保姆级教程:App开发新手入门(2)
上章节我们已经成功的创建了一个 App 项目,接下来我们讲述一下,如何导入项目、编辑代码和提交项目代码。 Let’s Go! 4. 项目导入 当用户创建一个新的应用时,YonStudio 开发工具会自动导入模板项目的默认代码,不需要手动进行代…...
sftp使用
Client端使用Server端的账户username,sftp登录Server,除了IP地址,也可以使用/etc/hosts定义的域名,注意,Client的默认路径:Shell中的当前路径,Server的默认路径:server账户家目录 …...
FastGithub---------不再为访问github苦恼
声明:只解决github加速神器,解决github打不开、用户头像无法加载、releases无法上传下载、git-clone、git-pull、git-push失败等问题。 github为什么打不开? 其实不用加速的情况下,使用5G是可以打开的,只是资源加载…...
Spring Boot AOP @Pointcut拦截注解的表达式与运算符
项目场景: 这里主要说下Spring Boot AOP中Pointcut拦截类上面的注解与方法上面的注解,怎么写表达式怎么,还有Pointcut中使用运算符。 PointCut 表达式 拦截注解的表达式有3种:annotation、within、target 1、annotation 匹配有…...
2023年第十四届蓝桥杯javaB组省赛真题
👨💻作者简介:练习时长两年半的java博主 📖个人主页:君临๑ 🎞️文章介绍:2023年第十四届蓝桥杯javaB组省赛真题 🎉所属专栏:算法专栏 🎁 ps:点…...
CefSharp.WinForms 112.2.70最新版体验
一、准备 下载最新包及依赖包(对应.NET4.5.2,后续版本可能4.6.2+)到packages中,本地升级更快 NuGet Gallery | CefSharp.WinForms 112.2.70 NuGet Gallery | CefSharp.Common 112.2.70 NuGet Gallery | cef.redist.x64 112.2.7 NuGet Gallery | cef.redist.x86 112.2.…...
Spring数据访问模块设计
前面我们已经完成了IoC和web模块的设计,聪明的码友立马就知道了,该到数据访问模块了,要不就这俩玩个6啊,查库势在必行,至此,它来了。 一、核心设计理念 1、痛点在哪 应用离不开数据(数据库、No…...
服务器--宝塔命令
一、宝塔面板安装命令 ⚠️ 必须使用 root 用户 或 sudo 权限执行! sudo su - 1. CentOS 系统: yum install -y wget && wget -O install.sh http://download.bt.cn/install/install_6.0.sh && sh install.sh2. Ubuntu / Debian 系统…...
【Go语言基础【12】】指针:声明、取地址、解引用
文章目录 零、概述:指针 vs. 引用(类比其他语言)一、指针基础概念二、指针声明与初始化三、指针操作符1. &:取地址(拿到内存地址)2. *:解引用(拿到值) 四、空指针&am…...
Python Ovito统计金刚石结构数量
大家好,我是小马老师。 本文介绍python ovito方法统计金刚石结构的方法。 Ovito Identify diamond structure命令可以识别和统计金刚石结构,但是无法直接输出结构的变化情况。 本文使用python调用ovito包的方法,可以持续统计各步的金刚石结构,具体代码如下: from ovito…...
云原生安全实战:API网关Envoy的鉴权与限流详解
🔥「炎码工坊」技术弹药已装填! 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、基础概念 1. API网关 作为微服务架构的统一入口,负责路由转发、安全控制、流量管理等核心功能。 2. Envoy 由Lyft开源的高性能云原生…...
HTML中各种标签的作用
一、HTML文件主要标签结构及说明 1. <!DOCTYPE html> 作用:声明文档类型,告知浏览器这是 HTML5 文档。 必须:是。 2. <html lang“zh”>. </html> 作用:包裹整个网页内容,lang"z…...
CentOS 7.9安装Nginx1.24.0时报 checking for LuaJIT 2.x ... not found
Nginx1.24编译时,报LuaJIT2.x错误, configuring additional modules adding module in /www/server/nginx/src/ngx_devel_kit ngx_devel_kit was configured adding module in /www/server/nginx/src/lua_nginx_module checking for LuaJIT 2.x ... not…...
JS面试常见问题——数据类型篇
这几周在进行系统的复习,这一篇来说一下自己复习的JS数据结构的常见面试题中比较重要的一部分 文章目录 一、JavaScript有哪些数据类型二、数据类型检测的方法1. typeof2. instanceof3. constructor4. Object.prototype.toString.call()5. type null会被判断为Obje…...
C++ 变量和基本类型
1、变量的声明和定义 1.1、变量声明规定了变量的类型和名字。定义初次之外,还申请存储空间,也可能会为变量赋一个初始值。 如果想声明一个变量而非定义它,就在变量名前添加关键字extern,而且不要显式地初始化变量: e…...
C++信息学竞赛中常用函数的一般用法
在C 信息学竞赛中,有许多常用函数能大幅提升编程效率。下面为你介绍一些常见函数及其一般用法: 一、比较函数 1、max()//求出a,b的较大值 int a10,b5,c;cmax(a,b);//得出的结果就是c等于10. 2、min()//求出a,b的较小值 int a1…...
