VR全景图片 USB串口通信 Java Spring jsp reactjs events playframework flexbox ACE matlab求矩阵最大值 mysql数据库驱动 mac脚本编辑器 python查找指定字符 python分析 python获取输入 python传递参数 java使用 java文件流 java连接mysql数据库 java入门课程 java对象是什么 java字符 java查看变量类型 制作字幕的软件 comsol软件下载 groupy 方正兰亭字体下载 怎么设置迅雷为默认下载器 tableau下载 go程序设计语言 灰色按钮激活精灵 备份数据的软件 编程电子书 losecontrol 向日葵9 浣海之核 c4dr20 摸摸头不哭表情包 方正倩体 网页播放器代码
当前位置: 首页 > 学习教程  > 编程语言

长链剖分(知识点整理+板子总结)

2020/10/8 18:12:16 文章标签:

思路来源 https://blog.nowcoder.net/n/5eaebd22f5f846838c637bc337cc1ee9 知识点整理 长链剖分,用于维护子树中只与深度有关的信息,多用于静态 长链剖分,顾名思义,每个点维护子树中最长的那一条链, [l[x],l[x]len…

思路来源

https://blog.nowcoder.net/n/5eaebd22f5f846838c637bc337cc1ee9

知识点整理

长链剖分,用于维护子树中只与深度有关的信息,多用于静态

 

长链剖分,顾名思义,每个点维护子树中最长的那一条链,

[l[x],l[x]+len[x]-1]是其长链区间,到l[x]的偏移量也确定了它的深度

和dsu on tree类似,但若干条链分别占用不同位置的数组空间,只有相同链的内存共用,

所以不用像dsu on tree那样清空内存,所以预处理长链长度之后,只需要三步

 

①搜长儿子,继承长儿子的答案

②把短儿子往长儿子上挂,计算短儿子的答案

③把自己这个节点挂上去

 

由于若干条长链不交,每个点在向上合并的时候,只会作为短链出现在一条链里,所以是O(n)的

似乎还是指针版的略快一点,然而习惯用数组下标写……

题目

n(n<=1e6)个点的树,

对于每个点,求其子树中出现节点最多的深度d,

如果存在多个深度,它们的节点个数相同,则返回最小的哪个

题解

搞个裸题,长链剖分合并,

首先继承长链答案,然后短链合并的时候,如果可更新则更新

最后check一下这棵子树的根的深度,判断其是否能更新答案

代码

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=1e6+10;
int son[N],len[N];//长儿子 
int n,u,v;
int l[N],r[N],dfn;//长链的dfs序区间段 
int sum[N],ans[N];
vector<int>e[N];
void dfs1(int u,int fa){
	for(int v:e[u]){
		if(v==fa)continue;
		dfs1(v,u);
		if(!son[u] || len[son[u]]<len[v]){
			son[u]=v;
		}
	}
	len[u]=len[son[u]]+1;
} 
void dfs2(int u,int fa){
	l[u]=++dfn;
	r[u]=l[u]+len[u]-1;
	if(son[u]){
		dfs2(son[u],u);
		ans[u]=ans[son[u]]+1;//答案来自长儿子 
	}
	for(int v:e[u]){
		if(v==fa || v==son[u])continue;
		dfs2(v,u);
		//答案来自短儿子 
		for(int j=l[v],k=1;j<=r[v];++j,++k){
			sum[l[u]+k]+=sum[j];
			if((k>ans[u] && sum[l[u]+k]>sum[l[u]+ans[u]]) || (k<ans[u] && sum[l[u]+k]>=sum[l[u]+ans[u]])){
				ans[u]=k;
			}
		}
	}
	sum[l[u]]++;
	if(sum[l[u]]>=sum[l[u]+ans[u]]){
		ans[u]=0;
	}
}
int main(){
	scanf("%d",&n);
	for(int i=2;i<=n;++i){
		scanf("%d%d",&u,&v);
		e[u].pb(v);e[v].pb(u);
	}
	dfs1(1,0);
	dfs2(1,0);
	for(int i=1;i<=n;++i){
		printf("%d\n",ans[i]);
	}
	return 0;
} 

 


本文链接: http://www.dtmao.cc/news_show_250008.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?