点分治模板 / p3806

前言

点分治好难Orz，感觉比SAM还难一些，模板码也有六七行的样子，学了好久…

点分治是一种解决树上点对、树上路径的问题的分治方法

由于树上数据难以存储至常规数据结构中，因此朴素做法往往有着难以接收的复杂度

而利用分支/二分思想，则可以降下一个数量级，可以处理大规模的树上问题，一般时间复杂度可以降至 O ( n log ⁡ n ) O(n \log n) O(nlogn)

那么接下来简要介绍一些这个的算法的流程以及实现

先推荐一个网址： bilibili点分治上面的up主讲的挺好

在了解点分治之前，需要有关于 树的重心 的前置知识

好下面来介绍它的具体流程，先放张经典的图： 点对数无非三种，如上述图所示，

首先第一步是决策 S 点选为何点，直观的可以感受到就是选择比较靠中心的点，我们一般用重心，方便求，也有着良好的时间复杂度，我们用getroot()这个函数去求它，大致流程是dfs遍历整个树，谁的最大子树的节点数最小，谁就是重心

选好 S 点后我们考虑上述三种情况，（1）好办，递归分治即可，（3）也好说，可以和（1）放在一块处理，关键是（2）这个不是很好解决

为此，我们专门构造一个函数calc()用来处理（2），具体想法是， S 的子树个数是有限的，那么我们挨个挨个来处理它的子树，

以下面的例题为例，要求满足 d i s ( i , j ) = k dis(i,j)=k dis(i,j)=k的点对，一个朴素的思想是，枚举不同子树的节点一一比较，但这样时间复杂度又变成 O ( n 2 ) O(n^2) O(n2)了，这样不好，点分治的处理手段是类似于分桶的思想，在处理子树时，把子树中所有结点到S的距离储存起来，将其存储至桶内

比如说当我们处理完（2）左面的子树后，再处理下面的子树，将下面子树的所有节点到 S 的距离求出来，假如对某个节点 W 它到 S 的距离为 d i s w dis_w disw​，而之前处理的子树中，又恰好有个节点 V 满足 d i s w + d i s v = k dis_w+dis_v =k disw​+disv​=k，那很好，我们把这个加到答案中，直至遍历完 S 所有子树的所有节点

到这里，整个过程差不多就要结束了，我们大致第可以感受到分治是如何对时间复杂度进行优化的，它类似于二分似的将整个树分为若干子树，子树内再递归处理，子树与子树之间则是难点，处理子树与子树间关系时，开了一个桶，开存储节点到 S 的路径，每处理一个节点时，对离线所存储的询问进行遍历，更新询问的答案，进而保障了时间复杂度还在 O ( n ) O(n) O(n)内

一、 例题 p3806

题目链接 洛谷p3806

二、 思路及代码 1. 思路

很经典的点分治入门题，求点对 (i, j) 距离 = k，是否存在

对calc函数进行稍较修改，套模板，即可

2. 代码

代码如下 ：

#include 
#include 
#include 
using namespace std;
const int maxn = 1e4 + 5;
const int maxk = 1e7 + 5;
struct e {
  int to, w, next;
} edge[maxn