轻重边树链剖分(HLD)课件

树链剖分（HLD）轻重边剖分河南省实验中学 zxy问题：给定一棵有n个节点、带边权的树，现在要对树进行m个操作，操作有2类：1、将节点a到节点b路径上所有边权的值都改为c；2、询问节点a到节点b路径上的最大边权值。请你写一个程序依次完成这m个操作。123456781091、修改2号到9号结点路径上的边值为7；546259133例：有三个操作2、修改2号到7号结点路径上的边值为4；3、查询9号到8号结点路径上的最大边权值。774每次修改和查询复杂度为每次修改和查询复杂度为O(n)。思考：既然每个操作都与树上的路径有关，能否思考：既然每个操作都与树上的路径有关，能否把这些路径分段存储，方便修改和查询？把这些路径分段存储，方便修改和查询？树链剖分 是指一种对树进行划分的算法，它先通过轻重边剖分（Heavy-Light Decomposition）将树分为多条链，保证每个点属于且只属于其中一条链，然后再通过数据结构（树状数组、SBT、SPLAY、线段树等）来维护每一条链。使用这种方法后，一般可以将修改和查询的复杂度降为O(logn)。(HLD)树链剖分的方法将树中的边分为：重边重边和轻边轻边定义size(X)为以X为根的子树的节点个数。令V为U的儿子节点中size值最大的节点，那么V称为U的重重儿子儿子，边(U,V)被称为重边重边，树中重边之外的边被称为轻边轻边，全部由重边构成的路径称为重重链链。性质：对于轻边(U,V)，size(V)maxsize7 then maxsizesizechild;8 sonxchild;第一次DFS代码 void dfs1(int x,int father,int depth)depx=depth;fax=father;sizex=1;for(int i=headx;i;i=nexti)int v=toi;if(v!=father)dfs1(v,x,depth+1);sizex+=sizev;if(sonx=-1|sizevsizesonx)sonx=v;链式前向星第二次DFS将重边连成重链：从根结点开始，沿重边向下扩展，连成重链；不能加入当前重链上的结点，以该结点为链首向下拉一条新的重链（如果该结点是叶子结点，则自己构成一条重链）；DFS过程中，对结点重新编号，因为是沿重边向下扩展，故一条重链上的结点新编号会是连续的。第二次DFSConnect_Heavy_Edge(x,ancestor)1 tidx+label;topxancestor;2 if sonx03 then Connect_Heavy_Edge(sonx,ancestor)4 while there exists a child of x not be visited5 do Connect_Heavy_Edge(child,child)12345678109第二次DFS代码 void dfs2(int x,int ancestor)topx=ancestor;tidx=+label;ranktidu=u;if(sonx=-1)return;dfs2(sonx,ancestor);for(int i=headx;i;i=nexti)int v=toi;if(v!=sonx&v!=fax)dfs2(v,v);重链剖分后：123456789101721083569413610782594tid1234567810917265381094rank 剖分完成后，每条重链相当于一段区间，将所有的重链首尾相接，用合适的数据结构来维护这个整体。例如：用线段树维护123456789101721083569413610782594tidrank1 0 12 5 23 1 34 3 45 5 56 9 67 4 78 2 89 3 910 6 101 5 26 9 71 5 34 5 56 9 89 6 101 5 56 9101910操作一：修改原树中某条边的权值直接在线段树中修改，并维护线段树（O(logn)）。12345678109546259133操作一：修改原树中某条边的权值例：将原树中的边(610)权值修改为6（边的权值已经存在该边所到达顶点中），10号结点的新编号为4。666操作二：修改原树中某条路径所有边的权值例：将原树中路径(29)上所有边的权值都修改为6，top2=top9=2，它们在同一条重链上，可以直接在线段树中修改。12345678109546259133操作二：修改原树中某条路径所有边的权值62号和9号结点的新编号分别为7和9，需要修改的区间为tidson2tid9，即8,9。6操作三：修改原树中某条路径所有边的权值例：将原树中路径(98)上所有边的权值都修改为6，top9=2,top8=8，它们不在同一条重链上，需要分段修改，边修改边往一条重链上靠。12345678109546259133第一步：dep8dep2,先修改8号点到其所在重链链首之间的边权值，对应线段树中tidtop8tid8,即区间8,8；然后通过top8的父结点3靠到3所在的重链上；6操作三：修改原树中某条路径所有边的权值例：将原树中路径(93)上所有边的权值都修改为6，top9=2,top3=1，它们不在同一条重链上，需要分段修改，边修改边往一条重链上靠。12345678109546259133第二步：dep2dep1,修改9号点到其所在重链链首之间的边权值，对应线段树中tidtop9tid9,即区间7,9；然后通过top9的父结点1靠到1所在的重链上；6666操作三：修改原树中某条路径所有边的权值例：将原树中路径(13)上所有边的权值都修改为6，top1=top3=1，它们在同一条重链上，直接在线段树中修改。12345678109546259133第三步：修改1号点到3号点间的边权值，对应线段树中tidson1tid3,即区间2,2的值，操作完成。66666修改某条路径上所有边权值(伪代码)change(x,y,w)/修改原图中x到y的所有边的权值为w 1 while topxtopy do 2 if deptopxdepy then swap(x,y)6 update(tidsonx,tidy,w)/update(l,r,w):将线段树中区间l,r的值修改为w。如果存的不是边权，而是点权，第6行应为update(tidx,tidy,w)操作四：查询原树中某条路径所有边权的最大值例：查询原树中2号到9号结点的路径中最大边权值，top2=top9=2,这两个结点在同一条重链中，对应的新编号分别为7和9，直接在线段树区间tidson2tid9中查询即可，即查询区间8,9中的最大值。操作五：查询原树中某条路径所有边权的最大值例：查询原树中路径(98)上所有边权的最大值，top9=2,top8=8，它们不在同一条重链上，需要分段查询，边查询边往一条重链上靠。12345678109546259133第一步：dep8dep2,先查询8号点到其所在重链链首之间的边权最大值，对应线段树中tidtop8tid8,即区间8,8，返回最大值9；然后通过top8的父结点3靠到3所在的重链上；ans:9操作五：查询原树中某条路径所有边权的最大值例：查询原树中路径(93)上所有边权的最大值，top9=2,top3=1，它们不在同一条重链上，需要分段查询，边查询边往一条重链上靠。12345678109546259133第二步：dep2dep1,查询9号点到其所在重链链首之间的边权最大值，对应线段树中tidtop9tid9,即区间7,9，返回最大值4(不优于ans当前值)；然后通过top9的父结点1靠到1所在的重链上；ans:9操作五：查询原树中某条路径所有边权的最大值例：查询原树中路径(13)上所有边权的最大值，top1=top3=1，它们在同一条重链上，直接在线段树中查询。12345678109546259133第三步：查询1号点到3号点间的边权最大值，对应线段树中tidson1tid3,即区间2,2的最大值，返回5(不优于ans当前值)，操作完成。ans:9查询某条路径上所有边权的最大值(伪代码)query(x,y)/查询原图中x到y的所有边权最大值 ans0 while topxtopy do if deptopx depy then swap(x,y)ans=max(tree_query(tidsonu,tidv),ans);return ans;/tree_query(l,r):在线段树的区间l,r中查询最大值。例 2015NOIPT6 运输计划 L 国有 n 个星球,还有 n-1 条双向航道,每条航道建立在两个星球之间,这 n-1 条航道连通了 L 国的所有星球。小 P 掌管一家物流公司,该公司有很多个运输计划,每个运输计划形如:有一艘物流飞船需要从 ui 号星球沿最快的宇航路径飞行到 vi 号星球去。显然,飞船驶过一条航道 是需要时间的,对于航道 j,任意飞船驶过它所花费的时间为 tj,并且任意两艘飞船之 间不会产生任何干扰。为了鼓励科技创新,L 国国王同意小 P 的物流公司参与 L 国的航道建设,即允许小 P 把某一条航道改造成虫洞,飞船驶过虫洞不消耗时间。在虫洞的建设完成前小 P 的物流公司就预接了 m 个运输计划。在虫洞建设完成后,这 m 个运输计划会同时开始,所有飞船一起出发。当这 m 个运输计划都完成时,小 P 的 物流公司的阶段性工作就完成了。如果小 P 可以自由选择将哪一条航道改造成虫洞,试求出小 P 的物流公司完成阶段 性工作所需要的最短时间是多少?【输入格式】第一行包括两个正整数 n、m,表示 L 国中星球的数量及小 P 公司预接的运输计划的数量,星球从 1 到 n 编号。接下来 n-1 行描述航道的建设情况,其中第 i 行包含三个整数 ai,bi 和 ti,表示第i 条双向航道修建在 ai 与 bi 两个星球之间,任意飞船驶过它所花费的时间为 ti。接下来 m 行描述运输计划的情况,其中第 j 行包含两个正整数 uj 和 vj,表示第 j 个运输计划是从 uj 号星球飞往 vj 号星球。【输出格式】共 1 行,包含 1 个整数,表示小 P 的物流公司完成阶段性工作所需要的最短时间。【样例输入】6 3 1 2 3 1 6 4 3 1 7 4 3 6 3 5 5 3 6 2 5 4 5【样例输出】11【样例输入】6 3 1 2 3 1 6 4 3 1 7 4 3 6 3 5 5 3 6 2 5 4 5【样例输出】11样例分析1263453476536：7+4=11 25：3+7+5=1545：6+5=11126345347651143236：7+4=11 25：3+7+5=1545：6+5=1126：3+4=714：7+6=1315：7+5=12分析：二分答案15 13 12 11 11 7 第一次二分答案ans=(0+15)/2=75条路径没有交集，此解不成立！条路径没有交集，此解不成立！126345347651032136：7+4=11 25：3+7+5=1545：6+5=1126：3+4=714：7+6=1315：7+5=12分析：二分答案15 13 12 11 11 7 第二次二分答案ans=(8+15)/2=113条路径有交集，交集中的最大边权值为条路径有交集，交集中的最大边权值为7，最长边最长边15-7=8，小于，小于11，此解成立！，此解成立！链式前向星把每条边按照起点和终点排序后存于一个数组中：同时，定义数组headi表示以i为起点的边集在数组中的第一个存储位置，比如head1=0;head3=4;leni表示以i为起点的边集在数组中的个数，比如len1=2;len3=3。这种存储图的方式为前向星，缺点是需要将边集排序，耗费时间。1213242536373859610012345678链式前向星改进：定义边的结构体struct Edge int w;int to;int next;edgem;edgei.to表示第i条边的终点；edgei.next表示与第i条边同起点的下一条边的下标；edgei.w为该边的权值；定义数组head,headi表示以i为起点的第“一”条边存储的位置，其实这是以i为起点的所有边中最后读入的那条，初值均为-1。链式前向星读入一条边，并存储：void add(int u,int v,int w)edgecnt.w=w;edgecnt.to=v;edgecnt.next=headu;headu=cnt+;链式前向星4623513592459361078-1-11-10-1-157428-136-1-1-1-112345678910head012345678nexttowedge读入顺序：1 2 42 4 62 5 25 9 31 3 53 6 16 10 33 7 53 8 9