树的常用算法.pptVIP

这是一个正确的贪心 S1：任选一个点u S2：BFS找出其最远点a S3：BFS找出离a的最远点b 则a与b则为树上最远点对 一个直接的想法是 opt[v]表示以v为根的子树中离v最远点到v的距离 opt1[v]表示以v为根的子树中离v次远点到v的距离 显然，我们可以简单的在线性的时间内处理出上面两个东西 对于一个点v，我们假设最长路经过这个点，那么就有两种可能 一、最长路在v这棵子树内 则长度为opt[v]+opt1[v] 二、经过v但不完全在这棵子树内 假设路径是从点x到点y的 设LCA(x,y) = p 则路径必然完全包含在p为根的子树内 一定在某次枚举中，被一所计算 要记录两个opt值，似乎上一种方法比较繁琐 试想，其实我们只要枚举每个点为根 假设枚举当前的根为v 那么只要求得当前的opt[v]，最后求出最大值 或者干脆换一个题目，要求求出每个点为起点的最长路长度 计算opt是很容易的 但是似乎这样的时间复杂度是O(N2)？ 我们观察一个比较简单的情况 可以发现，实质上这里以点1为根的子树只有3种本质不同的形态 根 边2,1 边4,1 可以发现除了根的情况，其实一般树形DP的本质状态都可以用边来表示——而不是点！ 对于一条边(u,v)其本质不同状态只有两种 u,v u是v的父亲 v,u v是u的父亲 因此，一般树形DP的本质不同状态只有O(N)种 其状态的多少和是否枚举根没有关系！ 回到原问题 我们只要枚举根，采用记忆化有哪些信誉好的足球投注网站的形式，用边表示状态计算opt数组即可 代码量，思维量大大减小！ 很优美的算法 空间复杂度是O(N) 时间复杂度也是O(N)？ 考察这样一棵树 对于任意一条边其转移时 涉及到的其他边数量为N-2=O(N) 有O(N)条这样的边，因此复杂度为O(N2) 分析原因： 考察点u 如果u的度为deg[u] 则存在deg[u]条连接u的边 每一条转移代价都是deg[u]-1 因此，总复杂度为 O(Σdeg[u]2)≈O(max{deg[u]}2)=Θ(N2) ε(deg[u]) = O(logN) 一般情况下上述算法效率非常高 很多情况下，这是性价比最高的程序书写方式 能否在理论上得到线性的解答？ 对于任意有根树，考察点v出发的最长路 为max{opt[v],非v子树内结点距v的最长路} 我们需要再做一次动态规划！ 令opt2[v]表示非v为根的子树中的点离v最远的距离 容易知道opt和opt1的计算是自底向上（即最早算叶子节点的值，最晚算根节点的值） 那么我们自上而下计算opt2 假设v的父亲为u 则opt2[v] = max (1) lenu,v + opt2[u] (2) lenu,v + opt1[u] | opt[u]来自子树v (3) lenu,v + opt[u] | opt[u]不来自子树v 对于贪心解法： 不得不承认的是由于树的优美性，很多DP解决的最优性问题放到树上都可以用贪心完美的解决，所以很多时候，对于树的问题下不了手的时候，不妨猜一个结论用贪心的方法尝试解决，很多时候，这就是正确的解法。 对于DP解法： 如果你细心观察的话不难发现，其实两个解法在做了一个本质一样的事情 同时最后一个解法给我们了一个很大的启示——就是按照什么顺序来拓扑有序的计算用边表示状态时的动态规划解 解法虽然有些麻烦但是却有很大的启发价值： 先自下而上，再自上而下 不难发现，树是一个二分图 因此一些特殊的二分图问题自然是可以在树上进行的，并且这一类问题由于树的优美性质而在难度上大大降低 二分图的最小覆盖问题是二分图经典问题之一 同样的，也可以在树上进行 问题： 选出最少的边，使得树上每一个点都被选中的边覆盖到，同时要求每个点至多被一条边覆盖 树形DP——不需要枚举根，用点记录状态即可 opt[v][0/1]表示覆盖v为根的子树，并且最后v(没有)被覆盖所需的最小边的数量 令c 为v的孩子，则 opt[v][0] = Σ{opt[c][1]} opt[v][1] = Σ{min(opt[c][0]+1,opt[c][1])} - max{opt[c][0]+1 – min(opt[c][0]+1,opt[c][1])} //至少要保证一个点和v相连边 有向拓扑图的最小路径覆盖是使用二分图匹配来解决的，树该如何呢？ 由于难度比较大，留给有兴趣的同学思考 思考题： 将树分成最少的链，使得每个点都被至少一个链覆盖，每个点最多属于一条链 提示： 使用左儿子右兄弟表示法将复杂度降低至O(N) 更难一点：你还能求出方案总数吗？ 排序二叉树是一类特殊的二叉树，每个结点有一个权值，并且对于一个子树保证根结点的左子树中任意结点的权值都不超过根结点权值，而右子树中任意结点的权值都不