有关树的算法.ppt

树树胜利一中王子昱概要概要?定义& 性质?树的遍历 o Dfs 序, Bfs 序& 欧拉序? LCA 问题?树形 DP ?*树分治?题目选讲定义定义& & 性质性质?定义(之一):联通、无环的无向简单图?每个顶点都是割点,每条边都是割边 o NOI07 追捕盗贼?在树上添加一条边会得到一个环 o在生成树相关的问题中很有用的性质?树是二分图?关键字 oN个顶点, n-1 条边的联通图 o任意两点间有且只有一条路径 o每个点向东至多连一条边([NOI2008] 道路设计) o Et cetera 树的遍历树的遍历深度优先遍历深度优先遍历?和图的 dfs 一致?先序遍历,中序遍历,后序遍历……? DFS 序 DFS DFS 序序深度优先遍历得到的序列: ? Dfs(x )o (x ) o For every child ch of x: ? Dfs(ch )o (x ) o记录第一次访问和最后一次访问 abeeffbcgghhiicdjjda ((()())(()()())(())) DFS DFS 序序:: :: 性质性质一棵子树对应一段连续的序列 oa beeffb cgghhiicdjjda o或者是 a bef cghidja ?例题 o给定一棵节点带权的树 o两种操作 o A I delta :以 I为根的子树内节点权值+delta o Q I: 求以 I为根的子树的权值和 o树状数组|线段树维护 dfs 序 abeeffbcgghhiicdjjda ((()())(()()())(())) DFS DFS 序序:: :: 性质性质?改动一下刚才的代码: ? Dfs(x )o ( +x ) o For every child ch of x: ? Dfs(ch )o ( -x )?考虑这个序列从+a 到+g 的和?+a +b +e – e +f – f – b +c +g ?正负抵消后就是从 a到g的路径! abeeffbcgghhiicdjjda ((()())(()()())(())) 例题例题?一棵节点带权的树,两种操作? A I delta: 点i的权增加 delta ? Q I j: 输出从 i到j的路径上点的权值和?直接套用刚才的方法? abeeffbcgghhiicdjjda ((()())(()()())(())) 例题例题?反例:从 e到c o +e –e– b +c ? e->c ? a->e + a->c – weight[a ] o (+a +b +e) + (+a +b +e – e +f – f – b +c) – a ? Q(u , v) = Q(w , u) + Q(w , v) – weight[w ], W = LCA(u,v ) o什么是 LCA ?一会再说……?树状数组|线段树维护 DFS 序 abeeffbcgghhiicdjjda ((()())(()()())(()))