点分治学习笔记

一、概述前置知识：树的重心。 1. 经典应用 1 假设a56爆大奖在线娱乐们要统计一棵有 $n$ 个节点的树上所有点对之间距离是 $k$ 的有多少对。注意树上的边有长度。 $n,k\le 10^6$。一个朴素的算法是遍历树上的所有点对，处理出距离（也就是链的长度）。时间复杂度 $O(n^2)$。考虑优化。由于