树链剖分
树链剖分
预备知识
引入
概念及定义如图,这是一棵树。 我们如果要按上面引入提到的内容操♂ 作它,咋办呢? 差分?LCA? 这些似乎都不好做,TLE,MLE欢迎你 所以,我们的树剖就闪亮登场了!它的好处就在于:把树简化为一条条的链,通过数据结构维护这一条条链 没错这就是树剖的概念,神奇海螺时间结束! 对于树剖算法,我们需要知道一些基本的数组及变量含义:
如上图,用黑线连接的结点都是重儿子,其余均是轻儿子,2-11就是重链,2-5就是轻链 如果你掌握了上面这些的含义,恭喜你,树剖入门完成50%! 题目了解了基本概念之后,我们来看一道模版题以此来继续下面的讲解... ...
0. 预处理
Dfs1void dfs1(int x,int fa,int dep) //当前点编号,父亲,深度(初始值:root,1) { d[x]=dep,size[x]=1,fat[x]=fa; //d[]:深度 fat[]:父亲 size[]:子树大小 int maxSon=0; //重儿子的子树大小 for(int i=head[x];i!=0;i=edge[i].next) { if(edge[i].to==fa) continue; dfs1(edge[i].to,x,dep+1); size[x]+=size[edge[i].to]; if(size[edge[i].to]>maxSon) maxSon=size[edge[i].to],son[x]=edge[i].to; //son[]:重儿子编号 } }
Dfs2void dfs2(int x,int tp) //x当前节点,tp当前链的最顶端的节点 { id[x]=++index; //标记每个点的新编号 val[index]=w[x]; //把每个点的初始值赋到新编号上来 top[x]=tp; //这个点所在链的顶端(重点数组!) if(!son[x]) return; //如果没有儿子则返回 dfs2(son[x],tp); //按先处理重儿子,再处理轻儿子的顺序递归处理 for(int i=head[x];i!=0;i=edge[i].next) { int y=to[i]; if(y==fa[x]||y==son[x])continue; dfs2(y,y); //对于每一个轻儿子都有一条从它自己开始的链 } } 线段树
1. 将树从x到y结点最短路径上所有节点的值都加上z
void update_link(int x,int y,int add) { while(top[x]!=top[y]) //当两点所处的链顶端的点不是一个点时,就一直往上跳 { if(d[top[x]]<d[top[y]]) swap(x,y); //记住:是深的往上跳 update(1,id[top[x]],id[x],add); //更新 x=fat[top[x]]; //跳到它链顶端的爸爸那 } if(d[x]>d[y]) swap(x,y); //为了保证id[x]<id[y] update(1,id[y],add); } 2. 求树从x到y结点最短路径上所有节点的值之和
int ask_link(int x,int y) { int ans=0; //记录答案用 while(top[x]!=top[y]) { if(d[top[x]]<d[top[y]]) swap(x,y); //原理同上 ans+=ask(1,id[x]); //累加 x=fat[top[x]]; } if(d[x]>d[y]) swap(x,y); ans+=ask(1,id[y]); //记得最后这还要加一次 return ans; } 3. 将以x为根节点的子树内所有节点值都加上z
4. 求以x为根节点的子树内所有节点值之和
总结至此树剖入门就结束了!恭喜完成树剖入门。下面有几道题不妨一做! 模版 [NOI2015]真题 思维题 快餐式的预备知识
dfs序
LCA
线段树
(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |