题意

给定一棵树和若干条路线，每条路线相当于  之间的路径，途径路径上的每个点。

【资料图】

给出若干个询问，每次询问从  到  至少需要利用几条路线。

Solution

考虑子问题，两个询问点在同一条链上，这样问题就类似 [SCOI2015] 国旗计划，只不过这道题是环上问题，但思路相同。

对于链，考虑贪心，对于每一个点  跳到能到达的最远的点 ，容易想到下一步应当是跳到 ，故考虑倍增优化这个不断往前跳的过程。定义  为点 i 跳  步能到达的最远节点，可以用  复杂度的时间来处理出  数组。

考虑树上的两个点，对于  是  的祖先节点（ 为  祖先节点时同理）的情况，同链上情况处理。

对于两个点分别不是对方父亲节点的情况，考虑将问题拆分为  到  和  到  两个问题处理。令 为  跳到  的最小步数， 为  跳到  的最小步数， 为  向上跳  步到达的深度最浅的节点，即跳到  的前一个节点， 同理。考虑两种情况：

有一条路线同时经过  和 ；

不存在一条路线同时经过  和 。

对于第二种情况，答案即为 ，对于第一种情况，答案为 。问题转化为如何维护是否存在一条路线经过两个点。

发现对于一个节点 ，只要 的子树中存在一个点，使得存在一条从其出发的路径在 的子树中结束，则存在一条路径同时经过 和 。考虑通过 dfs 序转化为区间问题，令  为节点  的子树大小，则问题进一步转化为询问是否存在一条路径  使得 。考虑二维数点，即查询平面上矩形  是否有点。将询问离线排序并用树状数组维护即可。

有个小细节：由于  和  在此题中是等价的，故在插入点时都应插入，否则可能会统计不到这个点。

其他具体实现细节见代码，以及由于我不会倍增求 lca，所以写了个树剖。

总时间复杂度应该是  的，但是有巨大常数，可以通过本题。

code

标签：