下面是一个点分治的计算过程展示,首先是找根,然后caldis算出所有基本路径,接着是算组合路径,然后删了这个根再递归其他结点,直到没有根可以递归为止
Root
基本路径
组合路径
1
(1,2)
(2,5)
(1,3)
(3,5)
(1,4)
(4,5)
(1,5)
2
(2,3)
(3,4)
(2,4)
5
无
无
3
无
无
4
无
无
在上表中,可以看出相比O(n*n)暴力算出所有路径的方法,只算基本路径并组合基本路径的方法可以将求路径这部分的复杂度降到O(n)
有了一个大概的思路后就是怎么实现的问题了.现在我们面临的问题是如何知道现在和曾经算出来的dis及其组合是否存在恰好等于k的点对.首先我们看看如何知道dis数组中是否存在距离为k的路径?很简单,每次算完dis后看他是否为k就好了.那么如何查询有没有现在处理出的某个dis与之前处理出的某个dis之和距离为k?首先我们会想到枚举现在的所有dis,再枚举之前的所有dis,这显然是个太暴力的方法,不可取.注意到dis[u]+dis[v]==k,如果我们现在已知k和dis[v],那么dis[v]就可以通过k-dis[u]求解出来.注意到若k==dis[u],则k-dis[u]==0,观察到题目上k的数据范围最大到1e7,如果开全局数组是存的下的.这里有个非常重要的点是注意不要数组越界,因为有可能算出来的dis是大于1e7的,但你又只开了1e7大小的数组,这样你就会RE.所以我们用数组来标记曾经处理过的距离,我把这个数组命名为jg,如果存在这个距离就打个存在标记,所以如果先把数组里的0标记后就可以统一用查找k-dis[u]是否存在来检测是否存在合法距离了.为了方便实现,我们通常会用一个数组把当前算出的所有dis记录下来,这样在点分治函数中判断的时候直接遍历这个数组就行了,注意这里要将询问离线,集中处理m次询问,调用1次点分治,如果调用m次点分治是会超时的.