树上启发式合并(dsu on tree)学习

声明:本文部分内容摘自OI Wiki网站。详情可自行查看学习。

洛谷 P9233

  题目实际上是蓝桥杯 2023 年 A 组省赛的一道题。题干大致的意思是,给定一个含有 n n n 个结点,并且以 1 1 1 为根的一棵树,每个节点 i i i 都有一个颜色 C i C_i Ci,问这棵树有多少个子树是颜色平衡树。其中,如果一棵树中存在的每种颜色的结点个数都相同,则我们称它是一棵颜色平衡树。
  输入:一行一个 n n n,后面的 n n n 行每行一个数对 ( C i , F i ) (C_i,F_i) (Ci,Fi) 分别表示结点 i i i 的颜色和父亲结点。(保证 F 1 = 0 F_1=0 F1=0)。
  输出:这棵树有多少棵子树是颜色平衡树。

题目分析

  感觉题目最大的难点是, C i ≤ 200000 C_i\leq 200000 Ci200000。因为我们最朴素的思想就是:看一棵树是否是颜色平衡树,需要将其子树的颜色情况统计起来。比如,开一个数组c[1..N],其中子树中颜色为i的结点有c[i]个。通过统计一棵树所有子树的c可以得到这棵树的c
  但是现在有一个问题,如果按照上面的思路,显然有 N ≥ C i N\geq C_i NCi;如果每碰到一个子树就开一个c[N],肯定会MLE,并且由于每次合并子树的颜色情况时需要遍历这个数组c,多半也会TLE。
  于是我们又产生了一个想法,用一个map来代替c[N]。因为不是每棵子树都会出现所有的颜色,我们开map不会为没有出现的颜色分配空间,显然空间使用就大大减少了。这种情况下合并子树的颜色情况时,只需要遍历所有子树的map,一一加到树上就行了。
  经过实践,使用map的方法确实不会MLE,但是它TLE了(70 pts)。

  接触到了树上启发式合并这一思想之后,迅速写代码,于是AC。树上启发式合并的核心思想就是保留重儿子。在下面的代码中有注释说明。

AC代码

#include<iostream>

using namespace std;

int n,c[200005],ccnt[200005],cccnt,sz[200005],ncolor[200005],ecnt=1,fedge[200005],ledge[200005],ans,bigchild[200005];
struct {
	int end,next;
}edge[200005];

void buildarc(int begin,int end){
	if(!begin)
		return;
	if(!fedge[begin])
		fedge[begin]=ledge[begin]=ecnt;
	else{
		edge[ledge[begin]].next=ecnt;
		ledge[begin]=ecnt;
	}
	edge[ecnt++].end=end;
}

inline void addcc(int cc){
	if(!ccnt[cc])
		cccnt++;
	ccnt[cc]++;
}
inline void delcc(int cc){
	ccnt[cc]--;
	if(!ccnt[cc])
		cccnt--;
}

void add(int node){
	if(c[ncolor[node]])
		delcc(c[ncolor[node]]);
	addcc(c[ncolor[node]]+1);
	c[ncolor[node]]++;
}
void del(int node){
	c[ncolor[node]]--;
	delcc(c[ncolor[node]]+1);
	if(c[ncolor[node]])
		addcc(c[ncolor[node]]);
}

inline int isbalanced(){return cccnt==1?1:0;}

// dfs0 用来求每个子树的大小的,也就是这个子树有多少个结点。
int dfs0(int cur,int father){
	int childsize,maxchild=0;
	sz[cur]=1;
	for(int e=fedge[cur];e;e=edge[e].next){
		if(edge[e].end==father)
			continue;
		sz[cur]+=(childsize=dfs0(edge[e].end,cur));
		if(childsize>maxchild){
			maxchild=childsize;
			bigchild[cur]=edge[e].end;
		}
	}
	return sz[cur];
}

// 这个是用来加入/删除某一棵树的,mod == 1 是加入,mod == 0 是删除。
void dfs2(int cur,int father,bool mod){//1 add 0 del
	if(mod)
		add(cur);
	else
		del(cur);
	for(int e=fedge[cur];e;e=edge[e].next)
		if(edge[e].end!=father)
			dfs2(edge[e].end,cur,mod);
}
/***
 dfs1 是树上启发式合并的核心算法。一个数有多个子树,其中最大的子树的树根成为这个树的重儿子,其它的儿子是轻儿子。树上启发式算法在每个子树上的操作分为 3 步:
 1.遍历所有轻儿子子树,查看情况,不保留轻儿子子树对原树 c[N] 数组的影响。
 2.查看重儿子子树的情况,并且保留该子树对原树 c[N] 数组的影响。
 3.重新加入所有轻儿子子树,从而得到原树的情况。

@param cur 当前结点
@param father 当前结点的父节点,用 father = 0 表示没有父节点
@param remain 是否要保留 cur 为根的子树对其父树的影响。也即 cur 是否是重儿子。
***/
void dfs1(int cur,int father,bool remain){
	//遍历所有轻儿子
	for(int e=fedge[cur];e;e=edge[e].next)
		if(edge[e].end!=father && edge[e].end!= bigchild[cur])
			dfs1(edge[e].end,cur,false);
	//查看重儿子
	if(bigchild[cur])
		dfs1(bigchild[cur],cur,true);
	//加入根节点
	add(cur);
	//重新加入所有轻儿子子树
	for(int e=fedge[cur];e;e=edge[e].next)
		if(edge[e].end!=father && edge[e].end!= bigchild[cur])
			dfs2(edge[e].end,cur,true);
	ans+=isbalanced();
	//如果要求不保留影响,cur 为根的树的所有贡献
	if(!remain)
		dfs2(cur,father,false);
}

int main(){
	int f;
	cin>>n;
	for(int i=1;i<=n;i++){
		scanf("%d%d",&ncolor[i],&f);
		buildarc(f,i);
	}
	return dfs0(1,0),dfs1(1,0,true),cout<<ans,0;
} 

  AC代码中保留了c[N]数组,其含义与上文所述相同,即颜色的出现次数。可以看到代码中还出现了ccnt数组和cccnt变量。这是一个比较精妙的处理方式,可以在 O ( 1 ) O(1) O(1) 的时间复杂度内判断一棵树是否是颜色平衡树。ccnt[i] = j表示当前共有j个颜色的c值是i,即颜色出现次数的出现次数cccnt颜色出现次数的出现次数的出现次数,当且仅当cccnt == 1的时候,该树是一颗颜色平衡树。
  上面的描述可能有些烧脑,可以用题目给的样例来说明。样例输入:

6
2 0
2 1
1 2
3 3
3 4
1 4

  读者可以根据输入的含义自行画图。对于根节点1而言,颜色1,2,3分别出现了2,2,2次,所以c[1,2,3] = {2,2,2}。根据定义,有3个颜色的出现次数是2,所以ccnt[2] = 3。而对于其它的i != 2,都有cccnt[i] = 0,所以cccnt = 1,因此该树是颜色平衡树。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/541172.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Spring框架第一篇(Spring概述与IOC思想)

文章目录 一、Spring概述二、Spring家族三、Spring Framework四、IOC思想五、IOC容器在Spring中的实现 一、Spring概述 Spring 是最受欢迎的企业级 Java 应用程序开发框架&#xff0c;数以百万的来自世界各地的开发人员使用 Spring 框架来创建性能好、易于测试、可重用的代码。…

Harbor私有镜像仓库

Docker私有仓库Harbor ​ 前面学习了Docker及Dockerfile构建镜像&#xff0c;那么构建的镜像放在哪里才能被Docker容器快速获取到呢&#xff1f;我们知道&#xff0c;可以把镜像放入Docker Hub镜像仓库&#xff0c;但是Docker Hub是国外网站&#xff0c;一方面镜像放在Docker …

童年女神大盘点:谁是第一个让你心动的动漫女神?

每当提起我们的童年记忆&#xff0c;总有一抹亮丽的色彩来自于那些国产动漫中的女性角色&#xff0c;她们以其独特的魅力、鲜明的性格和卓越的才智&#xff0c;深深地烙印在了我们的心底&#xff0c;成为了一代人的集体回忆。今天&#xff0c;让我们一同回首&#xff0c;盘点那…

napi系列学习进阶篇——NAPI异步调用

简介 OpenHarmony Napi 标准系统异步接口实现支持Callback方式和Promise方式。标准系统异步接口实现规范要求&#xff0c;若引擎开启Promise特性支持&#xff0c;则异步方法必须同时支持Callback方式和Promise方式。使用哪种方式由应用开发者决定&#xff0c;通过是否传递Call…

全新4.0版本圈子社交论坛系统 ,可打包小程序,于TP6+uni-app 全开源 可打包小程序app uniapp前端+全开源+独立版

简述 首先 圈子系统的核心是基于共同的兴趣或爱好将用户聚集在一起&#xff0c;这种设计使得用户能够迅速找到与自己有共同话题和兴趣的人。 其次 圈子系统提供了丰富的社交功能&#xff0c;如发帖、建圈子、发活动等&#xff0c;并且支持小程序授权登录、H5和APP等多种形式…

R语言记录过程

如何使用这个函数as.peakData 函数构造过程 出现问题是缺少函数的问题 up不告诉我&#xff0c;这里是代表c,h,o的值&#xff0c;你从里面获取把值&#xff0c;设置成c,h,o就可以了 现在开始测试参数 第一次 startRow : 开始查找数据的第一行。不管startRow的值是多少&#xff…

openstack-镜像服务 3

Glance镜像服务 创建glacnce数据库 创建glance用户并创建服务实体及api端点 安装glance软件包 修改配置文件 同步到数据库 设置开机自启并查看日志目录 使用测试镜像验证服务

10分钟带你学会配置DNS服务正反向解析

正向解析 服务端IP客户端IP网址192.168.160.134192.168.160.135www.openlab.com 一、首先做准备工作&#xff1a; 关闭安全软件&#xff0c;关闭防火墙&#xff0c;下载bind软件 [rootserver ~]# setenforce 0 [rootserver ~]# systemctl stop firewalld [rootserver ~]# y…

LeetCode题练习与总结:最小路径和--64

一、题目描述 给定一个包含非负整数的 m x n 网格 grid &#xff0c;请找出一条从左上角到右下角的路径&#xff0c;使得路径上的数字总和为最小。 说明&#xff1a;每次只能向下或者向右移动一步。 示例 1&#xff1a; 输入&#xff1a;grid [[1,3,1],[1,5,1],[4,2,1]] 输出…

超级详细的JDBC和数据库连接池讲解

文章目录 JDBC简介概念本质好处 JDBC快速入门JDBC中API详解DriverManager驱动管理类作用注册驱动获取连接 Connection数据库连接对象作用获取执行SQL的对象事务管理 Statement作用执行SQL语句 ResultSet原理使用步骤 PreparedStatementSQL注入获取对象操作步骤 原理好处 JDBC工…

项目管理-项目问题及需求解决要点

综上所述&#xff1a;在项目管理过程中&#xff0c;项目问题和需求逐渐增多&#xff0c;要不断的适应项目的种种&#xff0c;要想到如果没有问题要解决了&#xff0c;你的价值体现在哪里&#xff1f;要这样想&#xff0c;风险也是机会&#xff0c;所以问题等等也是自己的机会&a…

CopyTranslator下载地址及安装教程

CopyTranslator是一款免费且开源的机器翻译工具&#xff0c;旨在提供快速、便捷的翻译服务。它采用了先进的神经网络机器翻译技术&#xff0c;能够提供准确、流畅的翻译结果。 CopyTranslator的特点和功能如下&#xff1a; 多语言翻译&#xff1a;支持多种常见的语言对&#…

Unity让地图素材遮挡人物

点击编辑/项目设置/图形&#xff0c;透明度排序模式设置自定义轴&#xff0c;透明度排序轴Y设置为1其他为0。 此时人物和地图素材的图层排序相等&#xff0c;当人物的高度大于地图素材时&#xff0c;人物则被遮挡。

【零基础学数据结构】双向链表

1.双向链表的概念 1.1头节点 1.2带头双向循环链表 注意&#xff1a; 哨兵位创建后&#xff0c;首尾连接自己 1.3双链表的初始化 // 双向链表的初始化 void ListInit(ListNode** pphead) {// 给双链表创建一个哨兵位*pphead ListBuyNode(-1); } 2.双向链表的打印 // 双向…

Qlik在数据隐私计划中利用人工智能和分析

在技术快速变革的时代&#xff0c;政府正在努力追赶技术发展和我们日常生活中产生的个人身份信息&#xff08;“PII”&#xff09;数量不断增加的步伐。规范 PII 使用的隐私法不断加强&#xff08;Gartner估计&#xff0c;虽然到 2020 年&#xff0c;全面的隐私法将覆盖全球 10…

2024年广东省网络系统管理样题第1套网络搭建部分

2024年广东省职业院校技能大赛样题1 信息安全管理与评估 网络系统管理 网络搭建与应用 云计算 软件测试 移动应用开发 任务书&#xff0c;赛题&#xff0c;解析等资料&#xff0c;知识点培训服务 添加博主wx&#xff1a;liuliu5488233 网络系统管理赛项 模块A&#xff1a;网络…

Unity给地图物体添加对撞机

在项目/Assets下创建Prefabs文件夹 选择素材拖入层级下&#xff0c;注意此时地图素材有可能看不到&#xff0c;此时选择Tilemap在检查器中修改图层顺序调至最低。 添加对撞机 选择素材&#xff0c;在检查器中点击添加组件Box Collider 2D&#xff0c;将素材拖入Prefabs文件下…

C++ - 二叉搜索树的基本实现

目录 0. 引言 1. 二叉搜索树 1.1 定义 1.2 特点 2. 二叉搜索树的实现 2.1 基本框架 2.2 查找 2.3 插入 2.4 删除 2.4.1 右子树为空 2.4.2 左子树为空 2.4.3 左右都不为空 2.4.4 代码 0. 引言 在C语言数据结构中&#xff0c;我们已经基本了解过二叉树&#xff…

04异常Lambda算法正则

异常 异常是什么&#xff1f; 异常是代码在编译或者执行的过程中可能出现的错误。避免异常的出现&#xff0c;同时处理可能出现的异常&#xff0c;让代码更稳健。 异常分为几类&#xff1f; 编译时异常、运行时异常。编译时异常&#xff1a;没有继承RuntimeExcpetion的异常…

GB/T 28181标准中的错误码,国标28181中可能出现的SIP协议相关的错误码及其含义

目录 一、GB/T 28181标准介绍 &#xff08;一&#xff09;概述 &#xff08;二&#xff09;关键内容和特点 1. 系统架构&#xff1a; 2. 设备接入&#xff1a; 3. 网络通信&#xff1a; 4. 业务功能&#xff1a; 5. 安全保护&#xff1a; 6. 平台管理&#xff1a; &a…