树链剖分讲解
转载:http://blog.sina.com.cn/s/blog_6974c8b20100zc61.html
我们经常会遇到这样一类题目:给出一棵树,询问树上u,v两点路径间的最值,合值,更新u,v路径上的点权或边权,或者区间更新etc,此时如果单纯的用线段树或者树状数组去搞,很明显问题不能够得到完美解决,此时就需要更高级的数据结构去对树进行重新构造,也就是通常说的树链剖分。
一.树链剖分
树链剖分,顾名思义,也就是对树的每一条链进行剖分,将一棵树拆分成若干条链,对其进行重新编号,在进行了重新编号之后就可以用其他数据结构(线段树,树状数组,etc)去对数据进行有序化处理,这也就是说,大部分情况下,树链剖分是在为其他数据结构“打辅助”,和其他数据结构搭配起来使用才能更充分发挥它的作用。
剖树:
首先我们引入一些新的符号标记和一些概念
siz[i]:以i为结点的子树结点个数
son[i]:以i为结点的所有子结点中,siz最大的那个结点
Deep[i]:结点i的深度
fa[i]:i的父节点
top[i]:i结点重链上的顶端结点
重儿子:siz[u]为v的子节点中siz值最大的,那么u就是v的重儿子。
轻儿子:v的其它子节点。
重边:点v与其重儿子的连边。
轻边:点v与其轻儿子的连边。
重链:由重边连成的路径。
轻链:轻边,即非重边
对于一棵树来说,为了让他有序化,我们进行这样的操作:
1.找到每个结点的重儿子
2.将每个结点与重儿子组成重边,与其它结点组成轻边
3.对每个结点按重链深搜,轻边其次,进行重新编号映射
经过这样的操作之后,可以发现一棵树就被分为了重链和轻边,并且结点与结点之间要么是在同一条重链上,由重边相连接,要么不在同一个重链上,由重边和轻边交替连接。
代码实现:
第一步dfs 首先处理出fa,deep,siz,son ,这样预处理是为了在第二个dfs中直接沿着重儿子进行编号以处理重链编号。
- void dfs1(int k,int pre,int d)
- {
- deep[k]=d;
- fa[k]=pre;
- siz[k]=1;
- for(int i=fir[k];~i;i=nex[i])
- {
- int e=v[i];
- if(e!=pre)
- {
- dfs1(e,k,d+1);
- siz[k]+=siz[e];
- if(son[k]==-1||siz[son[k]]<siz[e]) son[k]=e;
- }
- }
- }
第二个dfs处理重链并对其进行编号,同时记录每个结点的top
- void dfs2(int k,int sp)
- {
- top[k]=sp;
- in[k]=tot++;
- if(son[k]==-1) return;
- dfs2(son[k],sp);
- for(int i=fir[k];~i;i=nex[i])
- {
- int e=v[i];
- if(e!=fa[k]&&e!=son[k])
- {
- dfs2(e,e);
- }
- }
- }
解释一下这样剖树的合理性:
首先这样剖完树后我们很容易观察到两个性质
性质1:如果(v,u)为轻边,则siz[u] * 2 < siz[v];
性质2:从根到某一点的路径上轻链、重链的个数都不大于logn。
现在考虑树上两点u和v的路径问题,由于子节点到父节点的路径是唯一的,而父节点到子节点的路径不唯一,我们让两点都到LCA上去,我们尝试让两点都到达LCA,根据以上的两个性质,我们最多经过logn条链就能让两个点在同一条重链上,这也就意味着我们仅仅花费了logn的复杂度就遍历了u到v的所有路径!!!问题就较完美的解决了。(下面会详细讲解爬树过程)
对一棵树进行剖分编号之后,还可以观察到:从根节点向下对所有结点的重链进行编号,的对于一条重链来说,其编号一定是连续的,对于一个结点来说,其子树的编号一定是连续的。
一棵树在剖完之后是这个样子:
红色代表重链,青色代表轻边,结点的编号是对链的重新编号。
这样剖完之后发现,对于重链来说完全可以将它映射到线段树上,这样就可以区间的去解决树链的问题,降低复杂度。
求LCA:
在找两点路径时,运用一种爬山的做法,每次将重链较深的结点优先向上爬,这样一直到两个结点都到达同一条重链上,相当于是在求LCA。
比如现在找4和7的LCA,那么路径是这样的:7->6->1,4->1
具体看代码
代码实现:
- long long Query(int s,int t)
- {
- long long sum=0;
- int f1=top[s],f2=top[t];
- while(f1!=f2)//使s,t向上爬到同一条重链
- {
- if(deep[f1]<deep[f2]) swap(f1,f2),swap(s,t); //深度较低的优先向上爬
- sum+=query(in[f1],in[s],1,tot-1,1);//统计答案
- s=fa[f1];
- f1=top[s];
- }
- if(deep[s]>deep[t]) swap(s,t);
- sum+=query(in[s],in[t],1,tot-1,1);///此时已经在同一条重链上了
- return sum;
- }
这里的向上爬是十分巧妙的,每一次让top较深的结点找到当前重链上的顶端结点直接跳跃向上爬,由于重链的编号又是连续的,所以又可以在线段树上直接进行区间统计,对于整颗树来说,相当于是logn的向上爬,对于统计答案来说,又是logn的在统计答案。试想如果每一次直接找每个结点的fa向上爬会怎样,很明显,复杂度大大超出,如果不让较深的结点向上爬会怎样,很明显,两点停在原链。