《有关树的算法》PPT课件.ppt
树,胜利一中 王子昱,概要,定义&性质树的遍历Dfs序,Bfs序&欧拉序LCA问题树形DP*树分治题目选讲,定义&性质,定义(之一):联通、无环的无向简单图每个顶点都是割点，每条边都是割边NOI07 追捕盗贼在树上添加一条边会得到一个环在生成树相关的问题中很有用的性质树是二分图关键字N个顶点，n-1条边的联通图任意两点间有且只有一条路径每个点向东至多连一条边(NOI2008道路设计)Et cetera,树的遍历,深度优先遍历,和图的dfs一致先序遍历，中序遍历，后序遍历DFS序,DFS序,深度优先遍历得到的序列:Dfs(x)list.push_back(x)For every child ch of x:Dfs(ch)List.push_back(x)记录第一次访问和最后一次访问,abeeffbcgghhiicdjjda()()()()()(),DFS序:性质,一棵子树对应一段连续的序列abeeffbcgghhiicdjjda或者是abefcghidja例题给定一棵节点带权的树两种操作A I delta：以I为根的子树内节点权值+deltaQ I:求以I为根的子树的权值和树状数组|线段树维护dfs序,abeeffbcgghhiicdjjda()()()()()(),DFS序:性质,改动一下刚才的代码:Dfs(x)list.push_back(+x)For every child ch of x:Dfs(ch)List.push_back(-x)考虑这个序列从+a到+g的和+a+b+e e+f f b+c+g正负抵消后就是从a到g的路径！,abeeffbcgghhiicdjjda()()()()()(),例题,一棵节点带权的树，两种操作A I delta:点i的权增加deltaQ I j:输出从i到j的路径上点的权值和直接套用刚才的方法？,abeeffbcgghhiicdjjda()()()()()(),例题,反例：从e到c+e e b+ce-c a-e+a-c weighta(+a+b+e)+(+a+b+e e+f f b+c)aQ(u,v)=Q(w,u)+Q(w,v)weightw,W=LCA(u,v)什么是LCA？一会再说树状数组|线段树维护DFS序,abeeffbcgghhiicdjjda()()()()()(),广度优先遍历,图的BFS使用队列BFS序,BFS序,广度优先遍历得到的序列Bfs(x)Que.push(x)While not Que.empty()Y=que.pop()List.push_back(y)For every child ch of yque.push(ch)同一深度的节点形成一个连续的区间Algorithm Engagement 2010 Firm这道题涉及的一些东西超纲了=,abcdefghij,欧拉序列,以根为起点的欧拉回路应用：LCA(最近公共祖先)问题：LCA(u,v)表示u和v的深度最大的公共祖先图中LCA(g,h)=c，LCA(g,j)=a给欧拉序列里的每个点加权，点i的权值是i的深度于是u,v的LCA是欧拉序列中u,v之间深度最小的点证明？,abebfbacgchcicadjda,e.g.abebfbacgchcicadjda0121210121212101210LCA(g,h)=c,树形DP,SPOJ PT07X,树的最小覆盖最小覆盖：选出点集的最小子集使得每条边至少有一个端点在该点集中二分图：转化为匹配f1i表示选择i时,以i为根的子树的最小覆盖;f0i表示不选i时的最小覆盖转移,SPOJ PT07Z,树的最长路一种优美的贪心算法两遍dfs应用了树的独特性质,不可推广DP任意选定一个根最长路一定是从一个点向下扩展出的最长路f和次长路g（如果有）的和只需要维护这两个量就可以了,最长路:推广,求出每个顶点出发的最长路定根之后，计算出从每个点向下的最长路f和次长路g点u的最长路可能是直接向下的(fu)，也可能是向上之后再向下(设为hu)怎么计算H？,最长路:推广,树形DP的推广,不一定是在树上进行的DpSDOI2010 Area题意：最大权独立集30%数据：图是一棵树Dp70%数据：图是基环+外向树的结构如果只有环该怎么做？100%数据：仙人掌,树形DP,大多数题目的套路是一样的自底向上自顶向下在状态中维护额外的信息点分治,题目选讲,树网的核NOIP2007,modified,给定一棵边带权的树，求出一条长=W的路径，使得到路径距离最大的点的距离最小N=300000,Next,树网的核Hint,证明：最优方案可以是直径的一段,直径的优美性质,Next,树网的核Solution,求出直径对直径上的点，计算disLeftx=x左端所有结点到x距离的最大值disRightx 同类disDev x=到直径的入口为x的所有点与x距离的最大值枚举+二分或单调队列计算答案O(NlogN)或O(N),Next,SPOJ PT07B,给定一棵树，找到它的最大的满足以下条件的子树：所有度大于2的点至多被两个度大于1的点连接.N=100000,Next,SPOJ PT07BSolution,“毛毛虫”如果毛毛虫没有足？最长路“足”的数目可以被附加到点上！设点u的权值为degu-2去掉所有权=0的点带权最长路,Next,SPOJ PT07F,树的最小路径覆盖选出数目最少的不相交路径，使得每一个节点都在一条路径上N=100000,Next,SPOJ PT07Fsolution,Next,SPOJ PT07I,一棵树上有m个蚂蚁窝蚂蚁i会在时刻Ti从窝Si里出来，以速度vi向窝Sj出发问有多少对蚂蚁在路上相遇M=1000,N=100000,Next,SPOJ PT07Isolution,枚举每对蚂蚁，判断是否相交计算一对蚂蚁路径的公共部分计算一个点到一条路径的“入口”分情况讨论,Next,树分治,超纲了 稍微提一下常见方法点分治边分治块分治(树块剖分)链分治(树链剖分),Next,点分治,选择一个点将无根树转为有根树递归处理去掉根之后的每一棵子树例题给定一棵树，点上带权求出所有长度=k的路径,Next,点分治 Cond,选一个根之后，路径可以分为经过根和不经过根的两种经过根的情况计算出当前子树中所有点到根的距离,用排序+扫描的方法求出和=k的点对数.注意到来自同一子树的点对是不合法的，所以需要减去同一子树里的答案不经过根的情况在子树中递归计算防止退化，根选取为当前子树的重心O(Nlog2N)树形Dp？,Next,边分治,在树中选取一条边将原有的树分成两棵不相交的树，递归处理。刚才的题?,Next,树块剖分,Next,SPOJ QTREE,一棵边上带权的树，两种操作CHANGE I ti 第i条边的权改为tiQUERY a b 求出a到b的路径上权最大的边,Next,SPOJ QTREE,Next,SPOJ QTREE,Query(a,b)While(roota!=rootb)/roota表示a所在树块的根If(deproota deprootb)Res=max(res,dataa)/dataa表示到块根的最大权值A=prerootaElseRes=max(res,datab)B=prerootbWhile(a!=b)If(depa depb)Res=max(res,weighta)/weighta表示a到prea的边权A=preaElseRes=max(res,weightb)B=prebReturn res,Next,Thanks for listening.,Questions are welcome.,
