文件名称：算法五基于链的分治-ansi-vita 62-2016 modular power supply standard
文件大小：2.84MB
文件格式：PDF
更新时间：2024-06-29 16:21:36
集训队论文集
4.3 算法五基于链的分治 考虑用链分治解决树上的 k = 3的带修改的问题。同样考虑直接对算法四的 DP进行优 化。首先处理完子树中的所有重链后，对于每一条重链，需要考虑的就是最高点在这条重 链上的所有连通子树。这棵子树和这条重链的交一定是重链上的一段区间，因此当考虑了 轻边子树的贡献后，每条重链上的问题就类似一个带点度限制的最大子段和问题了，同样 可以使用线段树维护。 同样设重链上的每个点按到根的距离从小到大的顺序分别是 p1, p2, ..., pc。对于每一 个线段树节点（设其区间为 [l, r]），记录以下信息（前提均为“所有节点都在 pl 的子树 中”）： • cro(a, b)：包括 pl 和 pr 、且 pl 的点度为 a、pr 的点度为 b的连通子图的最大权值和 • le f (a)：包括 pl 但不包括 pr、且 pl 的点度为 a的连通子图的最大权值和 • rig(b)：包括 pr 但不包括 pl、且 pr 的点度为 b的连通子图的最大权值和 • mid：既不包括 pl 也不包括 pr 的连通子图的最大权值和 这里的信息维护与最大子段和问题类似。在合并两个区间的信息的时候，枚举左右节 点的状态，判断中间的点度能否合并（合并需要在这两个点之间加一条边，因此需要判断 这两个点的点度是否均小于 k），若可以合并则更新合并后的状态。合并信息的复杂度为 O(k4)，可以使用前缀和优化至 O(k2)。 58