HDU 5977
POJ 1987
欢迎来到我的博客https://www.cnblogs.com/Railgun000
各位同学们大家好,今天我们来研究一下点分治.那么什么是点分治?顾名思义就是基于结点来分治,是树分治的一种,能够处理大规模的树上路径信息问题.
点分治比较模板化,通常分为3部分,分别是求解树的重心函数,计算所有结点到根节点的距离函数,还有点分治函数.
下面通过一道例题来感受一下
链接:https://www.luogu.com.cn/problem/P3806
给定一颗n个结点的无根树,有m次询问,每次询问树上距离为k的点对是否存在.第一行两个数 n,m。接下来 n-1 条边 a,b,c 描述 a 到 b 有一条长度为 c 的路径。接下来 m 行每行询问一个 K。对于每个 K 每行输出一个答案，存在输出 AYE，否则输出 NAY。
我们知道有根树是要有根的,所以我们先随便找一个点作为根rt.那么接下来的问题就是这颗树上有没有距离为k的点对.那么接下来看看会出现什么样的点对.对于当前根rt所有位于其子数中的路径可分为2种,一种是点对的路径经过rt,一种是路径不经过rt,如图所示,红色的就是路径.
对于路径经过rt的点对又可分为两种,根rt作为其中一端和两端都不是根rt,如图所示,红色的是路径,左图是根rt作为其中一端的情况,右图是两端都不是根rt的情况.
对于两端都不是根rt的情况,其实可以由根rt作为其中一端的路径,也就是基本路径合成,如下图所示.
由此我们发现,根rt作为其中一端的路径是最基本的一种情况,我们设dis[u]表示点u到rt的距离,因为路径两端都不是根rt的情况,其实可以由根rt作为其中一端的路径合成即u到v的距离为dis[u]+dis[v],而若路径不经过rt,但必定会经过当前树T中的某个点x,那么可将这个点x作为根结点形成一颗子树,转化为路径经过根节点的情况,并重新计算dis数组来求解.
到这里,我们想给这两种路径起一个名字,对于根rt作为其中一端的路径,我们称之为”基本路径”(为什么我给它起这个名字?因为这种路径对于这个问题来说是最基本的情况).对于这种两端都不是根rt的路径起一个名字,我们称之为”组合路径”(为什么我给它起这个名字?因为这种路径是有两条在不同子树中的基本路径组成的,注意这个组合路径的概念,我接下来会有解释)