[CSP-S2019] 树的重心 题解

csp,s2019 · 浏览次数 : 1

小编点评

## CSP-S2019 重心的思考与思考方法 **重心** 问题以枚举每条边找到重心,并利用 **倍增** 和 **信息化** 的技巧,最终在 O(n log n) 的时间中找到重心。 **思考步骤:** 1. **枚举每一条边**,每次扫一次的 **O(n^2)** 即可得到所有重心。 2. **优化** 寻找重心的 **倍增** 算法。 - **枚举** 重心所有 **O(n)** 个点的贡献。 - **信息化** 每种贡献的计算方式,以便在枚举过程中快速获得答案。 - **优化** 每个点的贡献,例如合并相邻的子树或考虑子树外的信息。 3. **选择最优解** 方法,通常是 **倍增** 和 **信息化** 的结合。 **关键优化方法:** * **倍增** : 通过枚举每个重心,建立一个 **倍增** 数组,方便在枚举过程中快速找到重心。 * **信息化** : 利用各种信息化技巧,例如枚举、分类、合并等,优化算法效率。 **最终结果:** O(n log n) **代码示例:** ```python def solve(n, edges): # 建立倍增数组 depth = [0] * n # 构建信息化数组 weight = [0] * n # 遍历每一条边 for i, edge in enumerate(edges): u, v = i // 2, i % 2 depth[u] += 1 weight[u] += weight[v] # 最终结果 return max(depth[i] for i in range(n)) ``` **总结:** 重心问题利用了枚举、信息化、倍增等多种技巧,最终在 O(n log n) 的时间中找到重心。通过细致的分析和优化方法,该算法展现出信息化与算法设计的重要性,以及在 CSP 考试中探索更多解法的技巧。

正文

[CSP-S2019] 树的重心

因为这道题令我十分兴奋,所以来写一下做完后的思考。

这道题用到了树的重心的种种性质,在写解法的时候会一一点出其用处。

首先,枚举每一条边,然后各自 \(O(n)\) 扫一次的 \(O(n^2)\) 做法是简单的。

那么接下来,就会出现不同的解法了:

  • 优化 \(O(n)\) 求解的过程至 \(O(\log n)\)

  • 利用 \(O(n)\) 状态 \(O(n)\) 求解的套路:枚举每一个的贡献。

那么接下来分开讲述两种做法


倍增优化求重心的过程

  • 如果 \(x\) 不为重心,那么重心要么在其重儿子内,要么在其子树外。

那么找一颗子树内的重心,就可以倍增求解了。

也就是删掉一个边 \((x, y)\) 之后(假定 \(y\)\(x\) 的父亲)\(x\) 子树内的重心是简单的,但是子树外(也就是 \(y\) 所在的子树)的重心不太好求解。

类似换根 DP 的思路,发现 \(y\) 所在子树的倍增数组,只会影响到 \(y\) 到根路径上的每一个点。

于是每一次 DFS 下去,\(O(\log n)\) 的更新倍增数组,然后 \(O(\log n + \log n)\) 的求两边的重心即可。


枚举每一个点的贡献

此时我们需要考虑的是一个点 \(x\) 如何变成重心。

  • 删除 \(x\) 子树中的某棵子树

  • 删除 \(x\) 子树外的某棵子树

  • 保留某一棵包含 \(x\) 子树

如果可以稍微合并一下,那么第二点和第三点是可以放在一起的。

但是如此分类讨论是相当难做的,考虑如何减少某一种状态。

  • 把两棵树通过一条边相连得到一棵新的树,则新的重心在较大的一棵树一侧的连接点原重心之间的简单路径上。如果两棵树大小一样,则重心就是两个连接点。

同理的,删除一棵子树,那么重心会向相离的方向移动。

那么删除 \(x\) 子树内的某棵子树,\(x\) 能够成为重心必须满足重心在 \(x\) 的子树内。

那么如果我们以某一个重心为根,意味着除了根,那么就没有满足上述条件的点了,此时我们只需要讨论子树外的情况即可。

  • 某个点是树的重心等价于它最大子树大小不大于整棵树大小的一半

假设我们删除了大小为 \(s\) 的连通块,那么 \(x\) 可以成为重心则需要满足:

\[\begin{cases} n - s - siz_x \le \left \lfloor \frac {n - s}{2} \right \rfloor \\ mx_x \le \left \lfloor \frac {n - s}{2} \right \rfloor \end{cases} \]

其中 \(siz_x\) 表示 \(x\) 所在子树的大小,\(mx_x\) 表示 \(x\) 子树的最大大小,也就是 \(mx_x = \max siz_y\)

稍微整理一下,就可以得到:

\[n - 2 siz_x \le s \le n - 2 mx_x \]

那么考虑 \(x\) 子树外有那些满足此条件的子树即可。

但是发现 \(x\) 的祖先 \(f\) 的大小并不可以是 \(siz_f\),而是 \(n - siz_f\),这是在 DFS 的过程中好维护的。

最终利用树状数组维护一下即可。

但是重心本身的答案并不能如此维护,我们需要单独做一次。

\(X\) 为重心 \(G\) 作为根的最大的子树,\(Y\) 为次大子树,那么对于某个点 \(x\) 需要分类讨论一下:

\[\begin{cases} \max (siz_X - s, siz_Y) \le \left \lfloor \frac {n - s}{2} \right \rfloor &\text{x 在 X 子树内} \\ siz_X \le \left \lfloor \frac {n - s}{2} \right \rfloor &\text{x 不在 X 子树内} \end{cases} \]

这是容易 \(O(n)\) 做一次的。

于是此算法的复杂度为 \(O(n \log n)\),代码应该不是很难。

可以参考代码内的注释:https://loj.ac/s/1911177

然而本算法仍然可以有优化的空间,可以参考 [CSP-S2019]树的重心 题解 - TEoS - 博客园,做到 \(O(n)\) 求解。


小小总结

本题可以说是非常开放的题,因为存在很多解法,这里并没有涵盖完。

足以说明在 CSP 考试中,不能局限于某一个算法,更多的尝试可能带来更多的解法。

而在本题中体现出了解决问题的常用思想:

  • 优化暴力 \(O(1) - O(n)\) 平衡为 \(O(n \log n) - O(\log n)\),也就是算法 1。

  • 多状态 \(O(n)\) 暴力求和转化为每一个元素的贡献。

  • 利用信息所附带的信息(性质)推导方向,优化代码。

倍增!非常优秀的一个做法,是考点的长青树。这需要重重注意,细细揣摩。

与[CSP-S2019] 树的重心 题解相似的内容: