2023-09-14

题目

P7215 [JOISC2020] 首都

难度&重要性(1~10):8

题目来源

luogu

题目算法

点分治

解题思路

一个显然的 \(O(n^2)\) 的暴力思路。
因为这是一颗树，我们就每一次将城镇 \(1\sim n\) 定为根节点，将这个城镇的所属城市定为首都，而要求首都的其他城镇到根节点的路径上只有首都自己的城镇。可事实上路径中是会出现其他的城镇的，我们就需要将这个挡路的城镇的所属城市合并掉。在合并的同时我们也需要将被合并的城市的城镇同样纳入首都，继续维护。
这个过程看似很繁琐，有点绕，其实我们只需要一个队列用来维护需要判断路径的城镇就可以了。而它的时间复杂度也非常好证明，因为每一个城镇最多入队一次，而我们需要枚举的只有根节点，时间复杂度为 \(O(n^2)\)。
好了，暴力讲完了，我们来讲一讲正解。
我们发现，我们每一次需要维护城镇到根节点的路径，保证没有其他城市的城镇。那么按照暴力的思路，我们每次需要维护相同城镇中点对的路径。考虑贪心，当我们选定城市 \(i\) 为首都，则答案一定不劣在选定其他城市为首都时将城市 \(i\) 合并的答案。
这样我们用点分治就可以解决了。