本题有虚树做法,基本思想差不多,但个人感觉还是换根树剖清真一点 233。

定义一组询问的根节点为这组询问的一号节点。

一个点会对答案产生贡献,当且仅当这个点到这组节点的其他节点的距离大于等于这个节点到这组询问的根节点的距离。

假设当前我们做到根节点为 $ root $ ,当前节点为 $ u $ 的情况,找出这条路径的中点为 $ mid $ ,那么肯定不会对答案产生贡献的点即整颗树 $ root $ 为根节点时 $ mid $ 这个节点的整颗子树。就是一个简单的换根树剖,乱搞一下即可。

先考虑 $|S| = 2$ 的情况:把原图缩成一棵圆方树,查询两点路径上的圆点个数(除去这两个点本身)。我们可以很方便的把这个性质拓展到 $|S|$ 为任意值的的情况,只要先差分出圆方树上每个点到根节点的圆点个数,然后把每次查询的点建出虚树,进行简单的树上差分即可。需要注意的是多组数据间的变量初始化,以及圆方树的节点个数是原来的两倍。

虚树学习笔记

题目先给定一棵树,然后每次询问和其中的一部分点有关的信息,且只考虑这些点和他们的 LCA 对答案没有影响,则可以考虑虚树。先求出所有点的欧拉序,把每次询问给出的点按照欧拉序排序,依次插入栈中,维护栈内元素使得形成一条在已插入的点中最右端的链。

其实没什么新知识,可以说是一种思想,所以代码也很好写,就是需要注意细节。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×