「洛谷日报第27期」点分治略解 点分什么意思

我给你讲，淀粉质可好吃了，真的。

点分治，是一种处理树上路径问题的工具，举个例子：

给定一棵树和一个整数 k ，求树上等于 k 的路径有多少条？

做法很简单，枚举不同的两个点，然后dfs算出ta们间的距离，统计一下就行了

大概是O(n^3)的复杂度

布星啊， n 大一点就搞不了了

那找个根，求出每个点到根的距离，然后枚举两个点，求 lca ，简单加减一下就行了

大概是 O(n^2logn) 的复杂度。。。？

还是布星啊 n 还要大，几万的数据就搞不了了怎么这么多事

考虑一下形成路径的情况，假设一条满足条件的路径经过点 x ，那么这条路径在 x 的一个子树里（以 x 为端点）或者在 x 的两个不同的子树里，如图：

一个好的想法是找到一个根，然后dfs遍历ta子树中的每个点，依次处理每个点的子树答案

- 原理

如图，假设我们选出一个根 Root ，那么答案路径肯定是要么被一个子树所包含，要么就是跨过 Root ，在黑子树中选择一部分路径，在红子树中选择一部分路径，然后从 Root 处拼起来形成一条答案路径

两种情况诶。。。分类讨论？

（分类讨论不会写的，这辈子都不可能写分类讨论的）

仔细想一下，发现情况1（被一个子树包含）中，答案路径上的一点变为根 Root ，就成了情况2（在两棵子树中）

如图， Root 为根的子树中存在答案（蓝色实边路径），可以看成以 Root2 为根的两棵子树存在答案，所以只用处理情况2就行了，可以用分治的方法，这应该是点分治的基本原理

先从找好一个根开始

- 选根（选重心）

首先根不能随便选，选根不同会影下面遍历的效率的，如图：

显然选 y 为根比选 x 为根不优，选 x 最多递归2层，选 y 最多递归4层

显然可以发现找树的重心（重心所有的子树的大小都不超过整个树大小的一半）是最优的

我们可以根据每个点子树大小确定根，当根的最大的子树最小时肯定是重心

一个简单的树形dp就能搞定

因为之后的分治过程还需要对子树单独找重心，所以代码中有use，但是开始对整棵树无影响

- 求距离

找到根了，现在我们可以dfs一遍重心的子树，求出重心到子树各个点的距离

然后可以枚举子树里的两个点，如果两个点到重心的距离和为k（题目要找距离为k的点对），那么答案+1

这是第二种情况，第一种情况就让距离根为k的点跟重心配对就行了，因为重心到重心的距离为0

如何统计答案呢？

- 统计答案

肯定不能直接枚举啊。。。n^2的复杂度啊喂

考虑枚举一个点，另一个点可以通过二分来求解，sort一下让距离有序，这样要找距离为k-枚举点的距离的点的个数，因为相同距离的点现在是连续的，所以可以二分出左右边界l,r，ans+=r-l+1

也可以通过移动两个指针来实现只要不是枚举两个点就行了

这样我们就快乐的A掉了这道题了吗？

求一遍发现答案不对诶。。。似乎多了几种情况。。。？如图：

假设 k =4，图中 A 到 Root 的距离为2， B 到 Root 的距离为2，合起来是4，这时候答案+1，但是显然这两个点最短路径不是4

这是因为ta们在同一子树中，到重心的路径有重叠部分

- 统计答案 二连击

处理方法：

1.可以求距离的时候把点染色，不同子树不同颜色，那么求答案的时候就得枚举每个符合答案的每个点看是否不在一个子树里

2.可以求当前点儿子的答案，统计儿子答案时各个点的距离加上儿子到根的距离，即把符合在一个子树条件的情况统计出来，最后这个点的答案减去儿子答案就行了

图中求 Root 儿子 son 的答案，因为加上儿子到重心的距离，所以 A 的距离还是2， B 的距离还是2，这样就把不符合条件的答案去掉了

这样答案就对了（写丑了就不怪我了）

- 复杂度

每次处理找树的重心，保证递归层数不超过 logn ，dfs求距离复杂度是 O(n) ，这里处理答案是 logn ，所以这个题总复杂度是 O(nlog^2n) 的。。。？反正过几万的数据是绰绰有余的（逃

推荐题：

模板题（雾）(https://www.luogu.org/problemnew/show/P3806)

模板题（求距离为k的点对个数）(http://codeforces.com/problemset/problem/161/D)

求小于k的点对个数(https://www.luogu.org/problemnew/show/P4178)

权值和为k，求最小边数(https://www.luogu.org/problemnew/show/P4149)

最后一题题(https://a-failure.github.io/2018/07/12/IOI2011-Race/)

本文发布于洛谷日报，特约作者：守望

原文地址：https://www.luogu.org/blog/user9012/dian-fen-zhi-lve-xie