点分治

例题：洛谷P4178 Tree
题意：求树上 \(\le k\) 的路径条数

点分治：
1·分治
从整棵树开始，不断分下去，每次统计过当前根节点的答案。

inline void dfs(int u, int SZ)
{
	vis[u] = true; //记录vis 
	ans += getans(u, k); //统计答案 
	int v;
	for(int e = hd[u]; e; e = nt[e]) //此时u就是rt，sz都是算好了的!!!!!!!
		if(!vis[v = to[e]]) //避免回交 
		{
	    	ans -= getans(v, k - (w[e] << 1)); //减去冗余答案 
			rt = 0, getrt(v, 0, sz[v]), dfs(rt, sz[v]); //递归子树重心 
		}
}

2·找重心
因为分治层数最多为n，而统计答案复杂度至少 \(\Theta(n)\)，不如利用这个与统计答案平行的时间点去找重心，这样每次 \(sz\) 减半，层数可以优化成 \(\Theta(log_n)\)
找重心应在 \(dfs\) 函数之前。
细节:
(1) \(rt\) 要更新成 \(0\)
(2) 要赋成新的 \(SZ\)，这里 \(getans\) 函数不会影响 \(sz_v\)，所以直接赋 \(sz_v\)

inline void getrt(int u, int fa, int SZ)
{
	f[u] = 0;
	sz[u] = 1;
	int v;
	for(int e = hd[u]; e; e = nt[e])
	    if((v = to[e]) ^ fa && !vis[v]) //避免回交 
	    {
	    	getrt(v, u, SZ);
	    	sz[u] += sz[v];
	    	f[u] = max(f[u], sz[v]);
		}
	f[u] = max(f[u], SZ - sz[u]);
	if(!rt || f[u] < f[rt]) rt = u;
}

3.计算和统计答案
遍历出子树需要的信息，然后合并子树信息
本题细节：
(1)算出每个点距离，从小到大排序。
(2)根也要在序列中，因为端点是根的也要算。
(3)刚开始写得太丑了，统计答案时还去重装桶，然后把距离相同和不同的分开算，一些运算调了很久。(我好弱啊) 其实就用双指针往中间扫，当和第一次 \(\le k\) 时，在满足的情况下一直跳，加上 \(tl - hd\) 即可（因为\(hd + 1\) 到 \(tl\) 都满足），由于跳的方向是恒定的，且是第一次满足要求，越往后跳越不容易满足要求，所以不会重也不会漏。

inline void getdis(int u, int fa, int tar)
{
	if(dis[u] <= tar) q[++cnt] = dis[u]; //距离入队 
	int v;
	for(int e = hd[u]; e; e = nt[e])
	    if((v = to[e]) ^ fa && !vis[v]) //避免回交  
	    {
	    	dis[v] = dis[u] + w[e];
	    	getdis(v, u, tar);
		}
}
inline int getans(int u, int tar)
{
	dis[u] = 0, cnt = 0, getdis(u, 0, tar); //算距离 ，此时不是从rt出发，因为减冗余答案时会直接用到v 
    sort(q + 1, q + cnt + 1);
	int hd = 1, tl = cnt, res = 0;
	while(hd <= tl) //排序指针扫 
	{
		if(q[hd] + q[tl] > tar) --tl;
		else res += tl - hd, ++hd;
	}
	return res;
}

4·容斥
由于距离这种东西是有信息丢失的，不能反映路径位置关系，所以统计的路径有可能相交。但是我们发现，相交只可能发生在同一子树内，所以我们对每棵子树求减去 \(u-v\) 路径长的两倍后的答案， 减掉它即可。（不用考虑相交两条及以上边的情况，因为它们会被相减消掉）

5·全局细节
(1)一定要用 \(vis\) 数组，不能只用 \(fa\) 判断往回走的情况，因为这里不是直接 \(dfs\)，而是按重心递归，所以 \(fa\) 和 \(u\) 不一定相邻，调用 \(getrt\) 和 \(getdis\) 函数时，过一层就没有上层 \(fa\) 的信息保存了，会出错。
所以调用 \(getrt\) 和 \(getdis\) 函数时，一定要判断 \(!vis_v\)
(2) 调用 \(getans\) 函数时，起始点不一定是 \(rt\)，因为此函数还有容斥的功用，其起点不一定是 \(rt\) 。把要用的起点弄进去，写 \(“u”\) 就行了。

总代码：

inline void getrt(int u, int fa, int SZ)
{
	f[u] = 0;
	sz[u] = 1;
	int v;
	for(int e = hd[u]; e; e = nt[e])
	    if((v = to[e]) ^ fa && !vis[v]) //避免回交 
	    {
	    	getrt(v, u, SZ);
	    	sz[u] += sz[v];
	    	f[u] = max(f[u], sz[v]);
		}
	f[u] = max(f[u], SZ - sz[u]);
	if(!rt || f[u] < f[rt]) rt = u;
}
inline void getdis(int u, int fa, int tar)
{
	if(dis[u] <= tar) q[++cnt] = dis[u]; //距离入队 
	int v;
	for(int e = hd[u]; e; e = nt[e])
	    if((v = to[e]) ^ fa && !vis[v]) //避免回交  
	    {
	    	dis[v] = dis[u] + w[e];
	    	getdis(v, u, tar);
		}
}
inline int getans(int u, int tar)
{
	dis[u] = 0, cnt = 0, getdis(u, 0, tar); //算距离 ，此时不是从rt出发，因为减冗余答案时会直接用到v 
    sort(q + 1, q + cnt + 1);
	int hd = 1, tl = cnt, res = 0;
	while(hd <= tl) //排序指针扫 
	{
		if(q[hd] + q[tl] > tar) --tl;
		else res += tl - hd, ++hd;
	}
	return res;
}
inline void dfs(int u, int SZ)
{
	vis[u] = true; //记录vis 
	ans += getans(u, k); //统计答案 
	int v;
	for(int e = hd[u]; e; e = nt[e]) //此时u就是rt，sz都是算好了的!!!!!!!
		if(!vis[v = to[e]]) //避免回交 
		{
	    	ans -= getans(v, k - (w[e] << 1)); //减去冗余答案 
			rt = 0, getrt(v, 0, sz[v]), dfs(rt, sz[v]); //递归子树重心 
		}
}