点分治 学习笔记

0. 点分治的用途
点分治可以解决树上的关于路径的问题，例如 洛谷P4178 Tree。(题目大意：给定一棵 /(n/) 个节点的树，每条边有边权，求出树上两点距离小于等于 /(k/) 的点对数量)这道题如果使用 /(O(n^2)/) 的暴力算法 显然 会T飞 ，然而之后您就会看到，点分治算法可以在 /(O(n/log^2 n)/) 的时间复杂度内解决它。
1.思想
顾名思义，点分治使用了分治的思想，把原问题拆分成若干个子问题，分别求解后再合并。把大象装进冰箱里需要几步？
1.1. 分
注意到如果指定一个节点为根节点，那么一个路径有可能有以下两个来源：
1.路径经过根节点； 2.路径完全被子树包含。
到这里一个分治算法已经呼之欲出了——可以递归地处理第二种情况，只需要在算法中考虑第一种情况就可以了。
1.2. 治
第二种情况可以递归地处理，并且递归到叶子节点时就不需要考虑第二种情况了(根本没有子树)，所以这里主要考虑第一种情况。
按顺序考虑每一个子树，用一个树状数组(或者是一个别的什么数据结构)来维

点分治 学习笔记最先出现在Python成神之路。