这里要注意一个问题,如果一个路径是组合路径,那么组成这条路径的两个基本路径必在以rt孩子结点ch组成的不同子树中.可以用反证法证明,如果在同以子树中选择两个不同的基本路径,那么这两条基本路径必定会有共同的rt与ch的边,那么这两个基本路径组成的就不是一条简单路径(就是没有重复边的路径),如图所示.
所以在同一子树中我们检查基本路径是否合法,在不同子树中的基本路径才可以两两组合成为组合路径来检查路径是否合法.
那么这个dis数组该如何计算?我们知道dis[u]代表u到rt的距离,同时我们还已知父结点与子结点间的距离,也就是边权.所以如果这个结点u是rt的孩子,那么dis[u]==边权.如果要求u的孩子v到rt的距离dis[v]呢?那么就是dis[v]=dis[u]+u到v的边权,这是一个自顶向下的过程,如此递推下去,就可以计算出dis数组,既然要递归,那我们就写个函数,这就是点分治中的计算所有结点到根节点的距离函数,当然这个只是基本部分,我们后续还要对这部分进行修改.
现在我们知道了路径的几种组成,知道了dis数组该怎么算,接着就要来解决这颗树中是否存在距离为k的点对.对于经过根rt的路径,我们可以枚举其子结点ch,以ch为根的ch子树(ch结点及其后裔结点)计算ch子树中所有结点到rt的距离dis,每次处理完dis数组后都看看现在和曾经处理出的dis中有没有距离为k的点对,或者是有没有现在处理出的某个dis与之前处理出的某个dis之和距离为k.如果有就将答案记录下来.rt的ch结点都处理完后就删掉rt结点(就是以后不要访问这个结点了,可以用删除标记数组来实现),以各个ch结点为新的根节点,对各个ch子树进行上述处理.这里的dis与之前处理过的dis组合就是之前说的在不同子树中的基本路径才可以两两组合来检查路径是否合法,可以说曾经处理过的基本路径必定与当前的基本路径在以rt的孩子ch结点形成的不同的子树中.
这里处理的过程简单的来说就是选一个根结点rt,然后算出所有基本路径和所有组合路径,同时处理这些路径,处理完后删掉这个结点找下一个根节点重复上述操作,直到没有结点可找.