文件名称：算法三点分治-ansi-vita 62-2016 modular power supply standard
文件大小：2.84MB
文件格式：PDF
更新时间：2024-06-29 16:21:35
集训队论文集
3.1 算法二树上的暴力 子任务 2中，数据范围支持每次修改 O(n)的算法。 这个问题满足最优子结构的性质，因此可以考虑使用动态规划算法。随意选取根节点 r将树转为有根树，设 Ch(i)为点 i的孩子节点集合。设 f (i)表示 i子树中距离 i最远的点的 距离20，g(i)表示完全在 i子树中的最长链的权值，则 f (i) = vi + max p∈Ch(i) f (p) g(i) = max ( f (i), max p∈Ch(i) g(p), vi + max p,q∈Ch(i)|p,q ( f (p) + f (q)) ) 只需要在 f (i) 和 g(i) 中同时记录方案数即可求出最优解的方案数，答案就是根节点 r 的 f (r)及其方案数。 在每次修改的时候，我们只需要更新 p到根节点 r 的路径上的 DP值即可，单次修改 的时间复杂度为 O(n)。 复杂度 O(n) + O(n) + O(n)，可以通过子任务 2，可能可通过子任务 3，期望得分 18至 25分。 3.2 算法三点分治 子任务 3、4的修改次数和树的规模较大，考虑优化每次修改的复杂度。 这里的问题是一类路径统计问题，因此可以考虑使用点分治，其具体内容及实现方式 可以参考 [1]。在分治的过程中，只需要考虑过当前重心 g的所有路径的最长链及其方案数 即可。设重心 g的分支集合为 Br（其实就是当前连通块中 g连出的出边集合），设 f (i)表 示当前连通块中，以 g为根的 i子树中，距离 g最远的点的距离，则过重心 g的最长链为 max ( f (g), max p,q∈Br|p,q ( f (p) + f (q)) − vg ) 在每次修改的时候，考虑包括被修改的点 i所在的所有分治中的连通块，而这样的连 通块只有 O(log n) 个，因此可以一个个暴力修改。在每个连通块中，被修改的是以当前 g 为根、在 i子树中的所有点到 g的距离，并且修改为加上修改后 vi 和修改前的 vi 的差值。 20这里的距离定义为两点之间唯一简单路径上所有点的点权和 54