轻重边树链剖分(HLD).ppt

剖分方法分为：盲目剖分，随机剖分，和启发式剖分，依据轻重边进行剖分属于启发式剖分。 * 本例中9号结点的原编号与新编号恰好一样 * * 树链剖分（HLD）轻重边剖分 河南省实验中学 zxy 问题： 给定一棵有n个节点、带边权的树，现在要对树进行m个操作，操作有2类： 1、将节点a到节点b路径上所有边权的值都改为c； 2、询问节点a到节点b路径上的最大边权值。 请你写一个程序依次完成这m个操作。 1 2 3 4 5 6 7 8 10 9 1、修改2号到9号结点路径上的边值为7； 5 4 6 2 5 9 1 3 3 例：有三个操作 2、修改2号到7号结点路径上的边值为4； 3、查询9号到8号结点路径上的最大边权值。 7 7 4 每次修改和查询复杂度为O(n)。 思考：既然每个操作都与树上的路径有关，能否把这些路径分段存储，方便修改和查询？ 树链剖分 是指一种对树进行划分的算法，它先通过轻重边剖分（Heavy-Light Decomposition）将树分为多条链，保证每个点属于且只属于其中一条链，然后再通过数据结构（树状数组、SBT、SPLAY、线段树等）来维护每一条链。 使用这种方法后，一般可以将修改和查询的复杂度降为O(logn)。 (HLD)树链剖分的方法 将树中的边分为：重边和轻边 定义size(X)为以X为根的子树的节点个数。 令V为U的儿子节点中size值最大的节点，那么V称为U的重儿子，边(U,V)被称为重边，树中重边之外的边被称为轻边，全部由重边构成的路径称为重链。 性质：对于轻边(U,V)，size(V)=size(U)/2。 从根到某一点的路径上，不超过O(logN)条轻边，不超过O(logN)条重路径。 1 2 3 4 5 6 7 8 10 9 5 4 6 2 5 9 1 3 3 (HLD)树链剖分的方法 1 2 3 4 5 6 7 8 10 9 5 4 6 2 5 9 1 3 3 图中有5条重链： 1→3→6→10 2→5→9 4 7 8 每一条链首深度大于1的重链都可以通过其链首的父亲结点连到另一条重链上。 (HLD)树链剖分的方法 1 2 3 4 5 6 7 8 10 9 5 4 6 2 5 9 1 3 3 定义 size[i]:以结点i为根的子树中结点的个数； son[i]:结点i的重儿子； dep[i]:结点i的深度，根的深度为1； top[i]:结点i所在重链的链首结点； fa[i]:结点i的父结点； tid[i]:在DFS找重链的过程中为结点i重新编的号码，每条重链上的结点编号是连续的。 树链剖分的过程 两次DFS 第一次DFS找重边，顺便求出所有的size[i],dep[i],fa[i],son[i]； 第二次DFS将重边连成重链，顺便求出所有的top[i],tid[i]。 第一次DFS 1 2 3 4 5 6 7 8 10 9 Find_Heavy_Edge(x,father,depth) 1 fa[x]←father; dep[x]←depth; 2 size[x]←1; maxsize←0; son[x]←0; 3 while there exists a child of x not be visted 4 do Find_Heavy_Edge(child,x,depth+1) 5 size[x]+=size[child]; 6 if size[child]maxsize 7 then maxsize←size[child]; 8 son[x]←child; 第一次DFS代码 void dfs1(int x,int father,int depth) { dep[x]=depth; fa[x]=father; size[x]=1; for(int i=head[x];~i;i=next[i]) { int v=to[i]; if(v!=father) { dfs1(v,x,depth+1); size[x]+=size[v]; if(son[x]==-1||size[v]size[son[x]]) son[x]=v; } } } 链式前向星 第二次DFS 将重边连成重链： 从根结点开始，沿