蒟蒻浅谈树链剖分之一——两个dfs操作

树链剖分，顾名思义就是将树形的结构剖分成链，我们以此便于在链上操作

首先我们需要明白在树链剖分中的一些概念

重儿子：某节点所有儿子中子树最多的儿子

重链：有重儿子构成的链

dfs序：按重儿子优先遍历时的顺序

轻儿子的意思就与重儿子相反

首先是第一个dfs操作

在本次操作中，我们主要做的是处理所有节点的父亲，子树大小，重儿子，深度等操作

void dfs1(int now,int father,int deep) {tree[now].depth=deep;//初始化当前节点的深度，子树大小，父亲 tree[now].size=1;tree[now].fa=father;maxson=-1;for(int i=head[now];i;i=tree[i].next){int v=tree[now].to; if(v==tree[now].father)//因为练的是双向边，所以不免会练到自己的父亲节点，就跳过 {continue;}dfs(v,now,deep+1);tree[now].size+=tree[v].size;//累加子树的大小 if(tree[v].size>maxson){tree[now].son=v;maxson=size[v];}} }

接下来就是第二次dfs操作，将树剖分成链的过程

我们在这时就有一个非常重要的东西那就是dfs序

dfs序就是我们遍历时的顺序，在这里的遍历方式是二叉树的中序遍历

因为我们在树链剖分中是以重儿子优先

所以dfs序可能会与实际有出入

所以我们还需新开一个数组来维护新的dfs序

以便于我们的线段树操作

但蒟蒻太弱，以后再来讲套线段树的事情

我们先好好的剖分吧

void dfs2(int now,int topf)//从当前节点开始，topf为当前链的顶端 {tree[now].index=++TIME;//dfs序 w[tree[now].index]=tree[now].value;//维护 tree[now].top=topf;//初始化，链顶即为topf if(!tree[now].son)//没有重儿子就先不用便利了 {return;} dfs(tree[now].son,topf);//优先遍历重儿子for(int i=head[now];i;i=tree[i].next)//在处理其他的情况 {int v=tree[i].to;if(v==father||v==tree[now].son)//不能为自己的父亲节点，也不能为重儿子 {continue;}dfs(v,v);//在轻儿子那里新开一条链 } }

所以说两个dfs还是比较好理解的

关键的是在树链剖分里更好的套数据结构

欲知后事如何，请听下回分解！

 

转载于:https://www.cnblogs.com/LJB666/p/10540244.html

总结

以上是生活随笔为你收集整理的蒟蒻浅谈树链剖分之一——两个dfs操作的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。