代码编织梦想

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 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的一些弊端和不足来帮助大家能更简单、无痛的构建一个生产可用微前端架构系统。 所