参考蓝书发篇学习笔记。。。
一.算法梗概：
点分治是一种用于在一棵树上，无对路劲进行修改的操作，对某些具有限定条件的路径进行静态统计的算法。
点分治一般用来处理无根树，我们可以随意认定根节点。
二.实现过程：
我们拿一道例题来说一下：
P4178 Tree
我们认定根节点为 \(root\)，那么对于 \(root\) 而言，树上的路径有两种：
1.经过 \(root\) 的路径；
2.不经过 \(root\) 但包含在 \(root\) 的某棵子树内。
对于路径种类1，我们可以从 \(root\) 点出发，对整棵树进行 \(\text{dfs}\)，求出点 \(i\) 到 \(root\) 的距离 \(dis_i\)，同时可以求出 \(b_i\)，表示 \(i\) 属于 \(root\) 的哪一棵子树。特别地，\(b_{root}=root\)。
代码如下：
点击查看代码
inline void getdis(int x,int fa,int d,int from)
{
a[++now]=x,b[x]=from,dis[x]=d;
for(int i=head[x];i;i=e[i].nxt)
{
int y=e[i].to,z=e[i].len;
if(y==fa || vis[y]) continue;
getdis(y,x,d+z,from);
}
return;
}
而我们要统计的，就是满足如下所有条件的点对 \((x,y)\) 的数量：（1）\(b_x\ne b_y\)；（2）\(dis_x+dis_y\leqslant k\)
对于路径种类2，我们可以分治一下，将 \(root\) 的每棵子树递归处理。
那么我们最常见的 \(calc\) 函数的写法，就是指针扫描数组的方法