P7215

2023-09-14 题目 P7215 [JOISC2020] 首都 难度&重要性(1~10):8 题目来源 luogu 题目算法 点分治 解题思路 一个显然的 \(O(n^2)\) 的暴力思路。 因为这是一颗树，我们就每一次将城镇 \(1\sim n\) 定为根节点，将这个城镇的所属城市定为首都， ......

点分治。 考虑当前的分治重心的城市被完全联通。 这可以用队列接解决。每次放入一种城市，就把那些城镇的父亲加入队列，如果存在城镇不在当前分治重心的联通块内，那么说明必定存在另一个分治重心能算到它，直接退出即可。 剩下的和模板没有任何区别。 复杂度 $O(n\log n)$。 code: ```cpp ......