树链剖分

江苏省大丰高级中学蒋一瑶提要树链剖分相关概念树链剖分的实现例题总结一、树链剖分的相关概念剖分目的树路径信息维护。将一棵树划分成若干条链，用数据结构去维护每条链，复杂度为O(logN)。剖分方法盲目剖分随机剖分启发式剖分综合比较，启发式剖分是剖分时的最佳选择。轻边和重边将树中的边分为：轻边和重边定义size(X)为以X为根的子树的节点个数。令V为U的儿子节点中size值最大的节点，那么边(U,V)被称为重边，树中重边之外的边被称为轻边。轻边和重边粗边为重边。另外，我们称某条路径为重路径(也叫重链)，当且仅当它全部由重边组成。914312211轻重边路径剖分的性质轻边(U,V)，size(V)=size(U)/2。从根到某一点的路径上，不超过O(logN)条轻边，不超过O(logN)条重路径。二、树链剖分的实现重链剖分重链剖分的过程为2次DFS第一次：找重边第二次：连重边成重链重链剖分找重边一次DFS，可记下所有的重边。重链剖分FIND-HEAVY_EDGE(x,father,depth)1father→fa[x],depth→dep[x]21→size[x],0→maxsize,0→son[x],…3whilethereexistsachildofxnotbevisted4doFIND-HEAVY_EDGE(child,x,depth+1)5size[x]+=size[child]6ifsize[child]maxsize7thensize[child]→maxsize8child→son[x]重链剖分连重边成重链以根节点为起点，沿重边向下拓展，拉成重链。不在当前重链上的节点，都以该节点为起点向下重新拉一条重链。重链剖分CONNECT-HEAVY_EDGE(x,ancestor)1++label→tid[x],ancestor→top[x],…2ifson[x]≠03thenCONNECT-HEAVY_EDGE(son[x],ancestor)4whilethereexistsachildofxnotbevisted5doCONNECT-HEAVY_EDGE(child,child)重链剖分x123456789top[x]1134514141圈内的数字为原编号，圆圈旁边的数字为size值，粗线表示重边。13245679894312112圈内数字代表每个点的新编号tid。123456789维护重链剖分完之后，每条重链就相当于一段区间，用数据结构去维护。把所有的重链首尾相接，放到同一个数据结构上，然后维护这一个整体即可。修改操作单独修改一个点的权值根据新的编号直接在数据结构中修改就行了。修改操作整体修改点U和点V的路径上的权值I如果U和V在同一条重链上直接用数据结构修改tid[U]至tid[V]间的值。修改操作整体修改点U和点V的路径上的权值II如果U和V不在同一条重链上一边进行修改，一边将U和V往同一条重链上靠，然后就变成了I的情况。修改操作A.若fa[top[U]]与V在同一条重链上。修改点U与top[u]间的各权值，然后U跳至fa[top[u]，就变成了I的情况。fa[top[u]Vtop[u]U修改操作B.若U向上经过若干条重链和轻边与V在同一条重链上。不断地修改当前U和top[u]间的各权值，再将U跳至fa[top[U]]，直到U与V在同一条重链。Vtop[u]U修改操作C.若U和V都是向上经过若干条重链和轻边，到达同一条重链。每次在点U和点V中，选择dep[top[x]]较大的点x，修改x与top[x]间的各权值，再跳至fa[top[x]]，直到点U和点V在同一条重链。top[U]Utop[V]V修改操作情况A、B是情况C的比较特殊的2种。I也只是II的特殊情况。所以，这一操作只要用一个过程。修改操作CHANGE(x,y,d)1whiletop[x]≠top[y]2doifdep[top[x]]dep[top[y]]3thenSWAP(x,y),SWAP(gx,gy)4CHANGE-IT(tid[top[x]],tid[x],d)5top[x]→x6ifdep[x]dep[y]7thenSWAP(x,y)8CHANGE-IT(tid[x],tid[y],d)//CHANGE-IT(l,r,d)为数据结构的修改操作：将区间[l,r]上的所有权值改为d查询操作查询操作的分析过程同修改操作。题目不同，选用不同的数据结构来维护值。查询操作QUERY(x,y)1whiletop[x]≠top[y]2doifdep[top[x]]dep[top[y]]3thenSWAP(x,y),SWAP(gx,gy)4QUERY-IT(tid[top[x]],tid[x])5top[x]→x6ifdep[x]dep[y]7thenSWAP(x,y)8QUERY-IT(tid[x],tid[y])//QUERY-IT(l,r)为数据结构的查询操作，三、例题Queryonatree题意：一棵N(N=10000)个节点的树，每条边都有一个权值，要求进行两种操作：CHANGEiti：改变第i条边的权值为tiQUERYab：询问节点a和节点b之间的路径中权值最大的边的权值时限：5sQueryonatree样例输入：输出:1133121232QUERY12CHANGE13QUERY12DONE数据组数Nabc:表示节点a和节点b之间有一条权值为c的边对于每一个QUERY操作输出对应结果Queryonatree直接模拟操作，修改操作每次可以在O(1)做到，询问操作期望复度为O(log2N)，不过最坏的情况下会达到O(n)。显然，在大量询问的情况下，直接模拟操作会TLE。Queryonatree这是一道树链剖分的经典入门题。建立树，进行重链剖分，用数据结构维护重链，再进行修改操作和查询操作。比较理想的支持修改操作且维护区间最大值的数据结构是线段树。Queryonatree不过，题中需要维护的是边权。将边(fa[x],x)的权值，作为点x的权值。根节点权值为一个无限小的值。四、总结总结树链剖分在信息学竞赛中越来越多的被考到，也是解题很有用的工具。平时多写写，容易有感觉，提高正确率。注意学会缩代码和提高程序的效率。Questionsarewelcome.