代码编织梦想

Dsu On Tree 模板 CF600E Lomsat gelral

  • 我们显然要维护以每一个节点为根的子树内的颜色信息

  • 对于一个节点 u u u,我们已经知道他的儿子 a , b , c a,b,c a,b,c 子树的信息,如何将子树的信息转移到节点 u u u ?

    • 如图:
      在这里插入图片描述
  • 朴素的想法

    将所有子树的信息逐一传递给父亲:那么其时间复杂度为 s i z e ( a ) + s i z e ( b ) + s i z e ( c ) size(a) + size(b) + size(c) size(a)+size(b)+size(c) O ( n ) O(n) O(n) 的复杂度,那么维护整棵树就是 O ( n 2 ) O(n^2) O(n2) 的复杂度

  • 优化:

    • 我们现在的操作相当于将 a , b , c a,b,c a,b,c 三个结点的信息传递到节点 u u u 上,
      节点 u u u 的信息初始为空,为 [ R e d : 0 ] [ B l u e : 0 ] [ G r e e n : 0 ] [Red:0][ Blue:0][Green:0] [Red:0][Blue:0][Green:0]
      传递 a a a 后变为 [ R e d : 4 ] [ B l u e : 2 ] [ G r e e n : 0 ] [Red:4][Blue:2][Green:0] [Red:4][Blue:2][Green:0]
      传递 b b b 后变为 [ R e d : 6 ] [ B l u e : 2 ] [ G r e e n : 1 ] [Red:6][Blue:2][Green:1] [Red:6][Blue:2][Green:1]
      传递 c c c 后变为 [ R e d : 6 ] [ B l u e : 3 ] [ G r e e n : 2 ] [Red:6][Blue:3][Green:2] [Red:6][Blue:3][Green:2]

    • 我们不妨将 u u u 的初始信息设置为 a a a 的信息,再将 b , c b,c b,c 的信息传递给 u u u ,就等价于将 a , b , c a,b,c a,b,c 信息传到空的 u u u
      这样 u u u 初始为 [ R e d : 4 ] [ B l u e : 2 ] [ G r e e n : 0 ] [Red:4][Blue:2][Green:0] [Red:4][Blue:2][Green:0]
      传递 b b b 后变为 [ R e d : 6 ] [ B l u e : 2 ] [ G r e e n : 1 ] [Red:6][Blue:2][Green:1] [Red:6][Blue:2][Green:1]
      传递 c c c 后变为 [ R e d : 6 ] [ B l u e : 3 ] [ G r e e n : 2 ] [Red:6][Blue:3][Green:2] [Red:6][Blue:3][Green:2]
      两者效果完全相同,但后者复杂度为 s i z e ( b ) + s i z e ( c ) size(b)+size(c) size(b)+size(c)

    • 如果我们每次都选择将 u u u 初始设为子树结点最多的儿子(即重儿子),再逐一转移其余儿子 ( 即轻儿子),可证得最终维护整棵树的复杂度为 O ( n l o g n ∗ ( 转 移 复 杂 度 ) ) O(nlogn * (转移复杂度)) O(nlogn())

    • 根据以上思路,我们不难得到以下代码

// O(nlogn * logn)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=1e5+5;
int n,col[MAXN],siz[MAXN],ans[MAXN];
vector <int> G[MAXN];
map <int,int> cnt[MAXN]; //cnt[u][c] : u 子树内颜色为 c 的个数
int mx, mxson, sum;
void dfs(int u,int fa)
{
	//siz[u] : u 子树的大小
	//mxson : 子树结点个数最大的儿子(重儿子)
	siz[u]=1;
	mx=0, mxson=0;
	for(auto v:G[u])
	{
		if(v==fa) continue;
		dfs(v,u);
		siz[u]+=siz[v];
		if(siz[v]>mx) 
		{
			mx=siz[v];
			mxson=v;
		}
	}
	
	if(mxson != 0)// 初始设为重儿子的信息
	{
		cnt[u] = cnt[mxson];
	}
	
	cnt[u][col[u]] ++ ;
	
	//传递其余儿子(轻儿子)的信息
	for(auto v:G[u])
	{
		if(v==fa) continue;
		if(v==mxson) continue;
		for(auto x:cnt[v])
		{
			cnt[u][x.first] += x.second;
		}
	}
	
	//求出现次数最多颜色编号之和
	mx=0, sum=0;
	for(auto x:cnt[u])
	{
		if(cnt[u][x.first] > mx)
		{
			sum = x.first;
			mx = cnt[u][x.first];
		}
		else if(cnt[u][x.first] == mx)
		{
			sum += x.first;
 		}
	}
	ans[u] = sum;
}
signed main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>col[i];
	for(int i=1;i<n;i++)
	{
		int u,v;
		cin>>u>>v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dfs(1,0);
	
	for(int i=1;i<=n;i++)
		cout<<ans[i]<<" ";
	
}

-在这里插入图片描述

  • 这样仍然需要优化
    • 这时候我们的 cnt数组就应该只开一维
    • 这时我们思路的应变:
      • 对于遍历的一个结点 u u u
      • 遍历轻儿子,算出轻儿子的信息
      • 遍历重儿子,不消除影响
      • 统计轻儿子贡献,将轻儿子的信息传递给父亲 u u u
      • 更新 u u u 的答案
      • 删除轻儿子的影响(cnt数组只有一个,消除轻儿子对其他节点的影响)
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_73113801/article/details/127991993

dsu on the tree 学习笔记-爱代码爱编程

dsu貌似就是启发式合并的意思,大家都知道这个东西是很神奇的,把n^2级别的复杂度降到nlogn,特别厉害的。 考虑如下问题:一棵树,问以每个点为根的子树中,和它颜色相同的有多少个节点(n<=10w,颜色数因为可以离

[学习笔记]dsu on tree_北路人的博客-爱代码爱编程

dsu on tree BB dsu on tree 树上并查集? 其实这东西跟并查集一点关系都没有吧(可能是我太年轻 树上启发式合并 和莫队一样有着 看上去 貌似 特别 高深 的名字,其实就是XJB暴力 正

点分治&&DSU on tree学习笔记-爱代码爱编程

点分治 luoguの模板 题目描述 给定一棵有 n n n 个点的树,询问树上距离为 k

dsu on tree(树上启发式合并)学习笔记_minato_yukina的博客-爱代码爱编程

最近队友都学了这个算法,我也来凑个热闹学习一下. Dsu on tree:目前我的理解就是一种对树上利用轻重链的性质进行子树统计的一种优化方法 因为一些问题中,需要反复清空子树的一些信息,防止其对隔壁树的兄弟信息统计进行干扰

c语言学习笔记(一)_四瓣纸鹤的博客-爱代码爱编程

终于换了工作了,我准备开始重新建立自己的计算机知识体系,自底而上的开始充实自己的技术能力。 首先是底层计算机技术,包括计算机原理、操作系统、数据结构。这一切的理论实践,需要以C语言为基础,所以先学C语言。 学习C语言,我使用《C程序设计语言》这本书为起点,全书正文166页,每天一节,用80天学习完。 学习C语言第一天: 第一章 导言,首先是概要的介绍

plc学习笔记(二):plc结构(1)_liutangplease的博客-爱代码爱编程

目录:  PLC学习笔记(一):概述 PLC学习笔记(二):PLC结构(1) PLC学习笔记(三):PLC结构(2) 🦁🦝🐰 以下为正文🐺🐱🐶         PLC种类众多,但其组成结构和工作原理基本相同,主要由中央处理器CPU、储存器(ROM、RAM)和专门设计的输入/输出单元(I/O)电路、电源等组成。PLC内部框图如下图所示。

微前端——single-spa源码学习_drinkwater sun的博客-爱代码爱编程

前言 本来是想直接去学习下qiankun的源码,但是qiankun是基于single-spa做的二次封装,通过解决了single-spa的一些弊端和不足来帮助大家能更简单、无痛的构建一个生产可用微前端架构系统。 所

【jvm学习笔记】内存回收与内存回收算法 就哪些地方需要回收、什么时候回收、如何回收三个问题进行分析和说明_jvm老年代什么时候回收-爱代码爱编程

目录 一、相关名词解释垃圾收集常用名词 二、哪些地方需要回收本地方法栈、虚拟机栈、程序计数器方法区Java堆 三、什么时候回收1. 内存能否被回收内存中的引用类型引用计数算法

httpservlet学习中的常见问题(个人珍藏笔记)_httpservlet delete请求接收失败-爱代码爱编程

目录 一、HttpServlet 1.1核心方法 1.2、面试:谈谈Servlet的生命周期 二、HttpServletRequest 2.1、核心方法 2.2、如何获取请求头 三、HttpServletResponse 3.1核心方法 四、setCharacterEncoding和setContentType区别? 五、Json格

spring-爱代码爱编程

由于SpringBoot 对 Security 的支持类均位于org.springframework.boot.autoconfigure.security包下,主要通过 SecurityAutoConfiguration

html学习-爱代码爱编程

HTML开发代码构成 h5 开发,本质上就是编写一个 .html 格式的文档,最终通过浏览器执行该文档,那么一个 html 文档中都包含哪些代码 标签不区分大小写 <标签名 属性="值"></标签名> 元素可以省略结束标签 元素的属性可以省略属性值,例如disabled、readonly 允许属性

2023年 图表示学习、知识图谱相关sci专刊与会议整理_知识图谱期刊-爱代码爱编程

图相关技术方向 1 IEEE Transactions on Neural Networks and Learning Systems 专刊:图学习相关 网址:IEEE Transactions on Neural Networks and Learning Systems - IEEE Computational Intelligence Soc