CF983E NN country 题解

2023-08-17 02:07 作者:泉五第一深情 0人读过 | 我要投稿

题意

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

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

Solution

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

对于链，考虑贪心，对于每一个点 $to_i%E2%80%8B$ 跳到能到达的最远的点，容易想到下一步应当是跳到 $to_%7Bto_i%7D$ ，故考虑倍增优化这个不断往前跳的过程。定义 $jump_%7Bi%2Ck%7D$ 为点 i 跳 $2%5Ek$ 步能到达的最远节点，可以用 $%5Cmathcal%7BO%7D(n%5Clog%20n)$ 复杂度的时间来处理出 $%20jump%20$ 数组。

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

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

有一条路线同时经过 $pre_x$ 和 $pre_y$ ；
不存在一条路线同时经过 $pre_x$ 和 $pre_y$ 。

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

发现对于一个节点 $u$ ，只要 $u$ 的子树中存在一个点，使得存在一条从其出发的路径在 $v$ 的子树中结束，则存在一条路径同时经过 $u$ 和 $v$ 。考虑通过 dfs 序转化为区间问题，令 $size_i$ 为节点 $i$ 的子树大小，则问题进一步转化为询问是否存在一条路径 $(fr%2Cto)$ 使得 $dfn_%7Bfr%7D%5Cin%5Bdfn_x%2Cdfn_x%2Bsize_x-1%5D%20%EF%BC%8Cdfn_%7Bto%7D%5Cin%5Bdfn_y%2Cdfn_y%2Bsize_y-1%5D$ 。考虑二维数点，即查询平面上矩形 $%5B(dfn_x%2Cdfn_y)%2C(dfn_x%2Bsize_x-1%2Cdfn_y%2Bsize_y-1)%5D$ 是否有点。将询问离线排序并用树状数组维护即可。