资源描述：
《浅谈树链剖分实现与应用》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、浅谈树链剖分实现与应用树链剖分用來处理静态树上的询问。顾名思义，树链剖分的主要思想是把树划分成儿条互相连接的链，再对何条链分别用数据结构维护。划分的方法很多，但为了减少后而操作的时间复杂度，我们需要选取适当的划分方法。轻重边剖分是一•种很好的剖分方法。轻重边剖分即把树屮的边分为轻重两部分。具体的说：设SZ[i]为以i为根的子树的大小（结点总数），则若点x不是叶结点，则其子结点中SZ值最大的（注意，有多个SZ值戢大的子结点应任选一个，只能选一个，防止出现重链相交，引发歧义）点y,边（x,y）称为重边，其余的边
2、都是轻边。首尾相连的重边称为重链（注意一定是自上而下的），则一个很显然的性质是：从根结点到任意点i路径上的轻边与重链的总数都不会超过O（log2N）o然后，对每条重链上的边建立线段树，每当遇到改值操作，若是轻边就直接改，若是重边就在线段树里改；遇到找x、y路径上边权最人值的操作，只耍找到LCA（x,y）,然后从x、y开始沿着树边上溯到LCA（x,y）处，对于屮间的每条轻边和重链（线段树内）导出最人值即可。具体步骤:（1）输入部分：建立无根树；（2）预处理部分：分为6步：<1>利用BFS将无根树转化为冇根树，
3、同时求出冇根树中点i（根结点除外）到其父结点的边的编号（设为FA[i]）以及点i的深度（设为DEP[i]）；v2>自底向上计算每个点的SZ值，同时划分轻重边（对于有根树中的每条边设立Z域,为重边，Z=0为轻边）；<3>求出重链，建立线段树；<4〉对树进行DFS遍历，求出序列A；<5>求出序列A的倍增最小值,存放在A0叩里（注意:A和A0中记载的都是编号，而判定大小的关键字是深度）；<6>求tBLOG[i]=log2i（下取整）;（3）执行部分：对于询问操作，求LCA,不断上溯，对于重链在线段树里找即可，注意
4、线段树的左右端点，尤其是当UP在LCA之上时，只能上溯到LCA处。算法实现：〃节点的标号从1开始#inelude#includeusingnamespacestd;constintN=10000;//N为节点的个数structe{intv;e*nxt;}es[N«l],*fir[N];//邻接链表存边structnodeintis,rs;//左右儿子的F标,为表示空intI,r;〃区间的左右标号〃数据域，根据不同的需要添加，数据的down和update和线段树的无异in
5、tmid(){return(I+r)»1;}}nodes[N«l];intn,en;//n为点数,en为边数intque[N],par[N],dep[N],root[N],seg[N],st[N],ed[N],top[N]zsons[N],id[N];//que用于BFS,par记录父节点，dep记录节点的深度。root[i]为链i的根节点,seg用于在链上建线段树，//st[i],ed[i]分别为链i的左右端点，top[i]为链i的顶部的节点，sons[i]为节点i为根的了树大小〃id[i]是节点i所属的
6、链的标号,intln,ent,tr;//In是琏的个数，ent为节点的个数,tr是树的根节点inlinevoidadd_e(intuzintv){es[en].v=v;es[en].nxt=fir[u];fir[u]=&es[en++];}inlinevoidnewNode(int&id,intI,intr){nodes[cnt].Is=nodes[cnt].rs=-1;nodes[cnt].I=I;nodes[cnt].r=r;id=cnt++;}voidbuild(int&id,intI,intr){〃
7、在剖分岀来的链上构建线段树newNodefid,I,r);if(I>=r){//seg[l]为落在这个线段树节点上的原树中的节点return;}intmid=(l+r)»l;build(nodes[id].ls,I,mid);build(nodes[id].rs,mid+1,r);}voidinitTree()〃预处理〃由根BFS确定父亲(无根树亠有根树)intI,r,u,v,i;e*cur;I=r=0;que[r++]=tr;par[tr]=-1；dep[tr]=0;whilefl!=r){u=que[l
8、++];intg=1；for(cur=fir[u];cur;cur=cur->nxt){讦((v=cur->v)!=par[u]){que[r++]=v;par[v]=u;dep[v]=dep[u]+l;}}}〃计算子树大小for(i=1;i<=n;i++){sons[i]=1;id[i]=-l;}for(i=r-1;i>=0;i-){u=que[i];if(par[u]>=0){sons[par[u]]+=so
