Dsu on tree树上启发式合并经典例题算法代码剖析_DevourPower的博客-程序员ITS203

技术标签: 教学  训练  Div题解  

题目链接:E. Lomsat gelral
树上启发式合并,初见这个名字,我和大部分人一样望文生义觉得应该是子树信息的合并使用了一种“启发式”,相当于区间操作的线段树的Lzay标志一般,仅仅启发而不去真的合并。

然后我兴高采烈的学了一下发现其实就是一个暴力。一个优雅的暴力优化。

dsu on tree,dsu就是并查集,直译为树上并查集。(某L称该算法为静态链分治。

首先我们审视一下题目暴力的写法:
对于每个子树开一个桶或者对每个子树都清空一次桶,然后暴力跑得出空间为 N 2 N^2 N2 或者时间为 N 2 N^2 N2 。这明显是不可取的。然后考虑暴力的优化,那就是当k结点需要求解的时候,可以保留一个重儿子求解之后的桶不给他清空,然后合并其他轻儿子,也就是说
轻儿子会经历:求解,清空共2次
重儿子会经历:求解,共1次。

然后发现如果有轻儿子重儿子之分则树链不超过 l o g 2 N log_2N log2N高度,于是可以得出这个小小的优化竟然能够让 N 2 N^2 N2变成 N l o g 2 N Nlog_2N Nlog2N

这个题写法可以有两种:

#define X first
#define Y second
const int maxn = 1e5+10;
ll a[maxn];
vector <int >g[maxn];
int tong[maxn] ,sz[maxn] ;
ll ans[maxn] ;
bool cmp(int a,int b){
    return sz[a]<sz[b];}
int dfs1(int k,int last)
{
    
	sz[k]=1;
	for(int i =0;i<g[k].size();++i)if(g[k][i]!=last)sz[k]+=dfs1(g[k][i],k);
	return sz[k];
}
void add(int k,int last,int cut,pair<int ,ll>& rem)
{
    //把k子树所有结点存入桶中
	//cut =1表示入桶,0表示出桶
	tong[a[k] ]+=cut;
	if(tong[a[k] ]==rem.X&&cut==1)
	{
    
		rem.Y+=a[k];
	}
	else if(tong[a[k] ]>rem.X&&cut==1){
    rem.X=tong[a[k] ];rem.Y=a[k];}
	for(int i=0;i<g[k].size();++i)
		if(g[k][i]!=last)add(g[k][i],k,cut,rem);
}
pair<int ,ll> dfs2(int k,int last)
{
    
	//printf("to : %d\n",k);
	//对于k结点子树求答案;
	//函数返回值:_max 和 答案;对应rem.X和rem.Y
	//先对k儿子子树求答案,然后对最重儿子最后处理;
	sort(g[k].begin(),g[k].end(),cmp);
	if(sz[k]==1){
    tong[a[k]]++;ans[k] = a[k];return (pii ){
     1,a[k] };}
	pair<int ,ll> rem ={
    0,0};
	for(int i=0;i<g[k].size()-1+(k==1);++i)
	{
    
		rem = dfs2(g[k][i] ,k);//除了最后一步都为轻儿子,最后一步不清除.则rem保证为最后一个重儿子的结果,则可以支持后续操作
		if(i!=g[k].size()-2+(k==1))add(g[k][i],k,-1,rem);
	}
	//printf("%d %d %d\n",k,rem.X,rem.Y);
	tong[a[k]]++;
	if(tong[a[k] ]==rem.X)
	{
    
		rem.Y+=a[k];
	}
	else if(tong[a[k] ]>rem.X){
    rem.X=tong[ a[k] ];rem.Y=a[k];}
	for(int i =0;i<g[k].size()-2+(k==1);++i)
	{
    
		add(g[k][i],k,1,rem);
	}
	ans[k] = rem.Y;
	return rem;
}
int main()
{
    
	int n;read(n);
	for(int i= 1;i<=n;++i)read(a[i]);
	for(int i =1;i<n;++i)
	{
    
		int u,v;read(u);read(v);
		g[u].push_back(v);g[v].push_back(u);
	}
	//input finished
	//树上启发式合并
	dfs1(1,1);
	dfs2(1,1);
	for(int i =1;i<=n;++i)printf(" %lld"+(i==1),ans[i]);printf("\n");

}

#include<cstdio>
using namespace std;
typedef long long LL;
const int maxn=100000,maxe=maxn<<1;

int n,col[maxn+5],fa[maxn+5];
int E,lnk[maxn+5],son[maxe+5],nxt[maxe+5];
int si[maxn+5],SH[maxn+5];bool vis[maxn+5];
int MAX,num[maxn+5];LL sum,ans[maxn+5];

#define Add(x,y) son[++E]=y,nxt[E]=lnk[x],lnk[x]=E
void Dfs(int x,int pre=0)
{
    
    si[x]=1;fa[x]=pre;
    for (int j=lnk[x];j;j=nxt[j]) if (son[j]!=pre)
    {
    
        Dfs(son[j],x);si[x]+=si[son[j]];
        if (si[son[j]]>si[SH[x]]) SH[x]=son[j];
    }
}
void Update(int x,int f)
{
    
    if ((num[col[x]]+=f)>=MAX)  if (num[col[x]]>MAX)
        MAX=num[col[x]],sum=col[x]; else sum+=col[x];
    for (int j=lnk[x];j;j=nxt[j]) if (son[j]!=fa[x])
        if (!vis[son[j]]) Update(son[j],f);
}
void Solve(int x,bool fl=true)
{
    
    for (int j=lnk[x];j;j=nxt[j]) if (son[j]!=fa[x])
        if (son[j]!=SH[x]) Solve(son[j],false);
    if (SH[x]) Solve(SH[x],true),vis[SH[x]]=true;
    Update(x,1);ans[x]=sum;if (SH[x]) vis[SH[x]]=false;
    if (!fl) Update(x,-1),MAX=sum=0;
}
int main()
{
    
    freopen("program.in","r",stdin);
    freopen("program.out","w",stdout);
    scanf("%d",&n);for (int i=1;i<=n;i++) scanf("%d",&col[i]);
    for (int i=1,x,y;i<n;i++) scanf("%d%d",&x,&y),Add(x,y),Add(y,x);
    Dfs(1);Solve(1);for (int i=1;i<=n;i++) printf("%I64d ",ans[i]);
    return 0;
}

除去注释和下面的压行,下面仍然要多一点语句,主要是第一个代码使用了rem去处理合并轻儿子过程对父亲整个子树的答案更新情况,而下面的代码使用了一个数组记录每个节点的rem,使用额外的数组存储对于空间有一点占用,两边都可以的。下面空间多了N个pair,但是更加简短,推荐使用。

以第一个代码来说:
过程先使用dfs1求子树size。
然后add函数为增加整个子树信息进入桶中,或者从桶中删除整个子树信息。然后就是dfs2过程了
dfs2代码先:重载cmp函数然后sort排个序,先对轻儿子求答案,然后剩下最后一个重儿子求完答案并没有清空,也就是这一小段:

rem = dfs2(g[k][i] ,k);
 //除了最后一步都为轻儿子,最后一步不清除.则rem保证为最后一个重儿子的结果,则可以支持后续操作
 if(i!=g[k].size()-2+(k==1))add(g[k][i],k,-1,rem);

可以看到当出了这个循环,rem保存的是重儿子的答案,_max 和cnt都存在这个pair变量中了,然后桶中也仍保留重儿子的信息。
然后就是add轻儿子,并且add函数当cut为1,会更新通过引用传进去的rem,作为父亲节点子树的答案,然后返回父亲节点子树答案当做函数返回值。

至此,完成树上启发式合并这个名字听起来和算法过程没什么大关系的算法啦。

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/DevourPower/article/details/109614838

智能推荐

Keras中fit()和fit_generator()区别以及其参数的坑_MrLeaper的博客-程序员ITS203

fit和fit_generator的区别首先Keras中的fit()函数传入的x_train和y_train是被完整的加载进内存的,当然用起来很方便,但是如果我们数据量很大,那么是不可能将所有数据载入内存的,必将导致内存泄漏,这时候我们可以用fit_generator函数来进行训练。下面是fit传参的例子:history = model.fit(x_train, y_train, ep...

Scratch 3.0建站指南(一)_fancy_kevin的博客-程序员ITS203_scratch

Scratch 3.0建站指南(一)Scratch 3.0已经到来Scratch3.0 的用户界面发生了很大的改变,更便于使用和学习:接下来的内容中我们就讨论一下如何针对Scratch 3.0进行建站。建站之本地环境准备:在后边的章节我们将再讲一些关于生产环境部署,以及定制开发的内容。Scratch 3.0已经到来Scratch 3.0是下一代Scratch。它是Google的Blockly项...

深入MFC中WM_COMMAND命令消息的传递 _zhangxinrun_业余erlang的博客-程序员ITS203

<br />我们都知道,MFC将windows消息系统进行了高度的抽象和封装,其根本原理是运用C++的高级特性并结合一定的设计模式(如工厂模式,模板方法等)来实现的。一般的windows消息(WM_XXX),则一定是由派生类流向基类,没有旁流的可能。如果是命令消息(WM_COMMAND),那就有比较奇特的路线了。下面就针对多文档/单文档(Document-View)、对话框两种应用程序比较讨论WM_COMMAND消息的传递处理过程。讨论前首先得明确命令消息的来源,命令消息一般是用户选择某个菜单项,或一个加速

web前端开发技术(第3版)储九良著课后实验_过客的博客的博客-程序员ITS203_使用标题字和段落标记进行文字显示

实验71.使用内联样式表及内部样式表,设计7-9所示的页面。设计要求如下:(1)使用标题字和段落标记进行文字显示,在内部样式表中定义body标记内信息“居中显示”,定义p标记字体为“隶书”。(2)通过怕标记style属性定义字体大小属性(font-size)的值为150%,200%,250%,"朝辞白帝彩云间,"不定义任何任何样式。&lt;!DOCTYPE html&gt;&lt;html&gt;&lt;head&gt;&lt;meta charset="UTF-8"&gt;&lt;titl

win7 计算机管理的命令,win7 cmd命令大全_windows7的cmd命令有哪些_刘柏霄的博客-程序员ITS203

相信还有需要在使用win7系统,那么大家知道windows7的cmd命令有哪些吗?cmd命令可以快捷键打开设置,还可以用来修复电脑,也可以用cmd命令来删除文件,可以说cmd命令是非常方便的。下面我们就一起来看看win7 cmd命令大全。win7cmd命令大全:1、首先,我们要知道cmd的打开方式,win10可以通过win键+R打开运行。开始-运行-输入cmd即可打开。2、打开cmd就会出现一个黑...

C语言之预处理_zouye4456的博客-程序员ITS203

1 #define name value  我再学习预处理直接的驱动力是看了php的源码,开头一大推的宏定义器,之前'掌握'的一点#define的用法太少了,根本看不懂源码中宏的处理逻辑和运行的路径。所以再学习预处理器很有必要,里面好多东西其实并不难,只是你没有接触到,等你学习了,就感觉容易了。  一、宏定义和使用中的坑  这小节采用先给代码再说明的形式,这样你可以

随便推点

STM32用SPI方式控制OLED模块_yugang_123456的博客-程序员ITS203

https://blog.csdn.net/Zach_z/article/details/72902591

基于VC6.0的控制台作图--显示位图(bmp)_邵玉斌的博客-程序员ITS203

文章目录GDI是什么?用`LoadImage`读取位图bmp文件将位图选入内存兼容区将内存兼容区拷贝到屏幕区恢复现场销毁临时的内存DC实例 ( showbmp.cpp)进一步的改进方向GDI是什么?前面,我们利用windows的图形设备接口实现了在控制台窗口中作图和动画。其中,链接了gdi32.lib库,也就是使用了GDI(图形设备接口)。GDI在全称是Graphics Device Int...

Hibernate Validator_oklookmaomao的博客-程序员ITS203

用Annotations 给类或者类的属性加上约束(constraint),在运行期检查属性值是很优雅的.Hibernate Validator就是这样的一个框架.该框架是十分容易的(就像参考文档中宣称的那样),几乎没有什么学习曲线,Validator 是一个验证框架 不需要和Hibernate的其他部分绑定就可以使用,只要在你的项目中添加Hibernate-annotations.jar...

python可视化分析网易云音乐评论_python 网易云音乐 评论爬取问题_白庆堂的博客-程序员ITS203

除了使用phantomjs,selenium之外,怎么爬取多页评论,这两个都太慢了。例如http://music.163.com/#/song?i... 的 评论。webapi都是http://music.163.com/weapi/v1...,每页20个评论,怎么获取下一页的评论,param是加密的,post都不知道post什么数据在网上有一种方式只能获取def aes_encrypt(self...

备赛笔记:Opencv学习:直线检测_Raine_Yang的博客-程序员ITS203_opencv寻找直线

直线检测一般使用函数HoughLines或HoughLinesP,第二种方法为概率版本Hoygh变换,这个函数是优化版本,计算速度更快。参数2rho和theta,一般取值1和np.pi/180。把图像缩放为原来四分之一并转化为灰度图,以减小计算量。参数5最大线段间隙,大于该间隙会被认为是两条线。参数4最小直线长度,小于该长度会被忽略。使用HoughLineP提取直线。参数3阈值,低于该阈值会被忽略。使用Canny函数提取边缘。参数1要处理的二值图像。.........