“引爆逆天力量，追寻圆环之理的神藏奥秘”系列再现高手。

首先最终的树的点数可以达到 $10^{10}$ 级别，我们肯定不能真正把树建出来。

但是注意到我们可以只保留每个复制出的子树的根（记作关键点），那么这些根也构成一棵树，这样就好办了。

当询问 $dis(x,y)$ 时，我们先找到 $x$ 和 $y$ 分别从属于的关键点，并求出它们在关键点树上的距离，而这是容易预处理的。需要注意的是，在 lca 处涉及同一关键点范围内的距离，在原树上查其距离即可。

以及，在定位点时，涉及查询原树某棵子树内编号第 $k$ 大的点，把树拍成 dfn 序后主席树上二分即可。

时间复杂度 $O(n\log n)$，有点难写。

之前在 LOJ 上见过一道类似的 ROI 题。

警告一次，教室再出现恶意刷屏，全部踢出去，你们代表的是CCF的形象。警告一次，教室再出现恶意刷屏，全部踢出去，你们代表的是CCF的形象。警告一次，教室再出现恶意刷屏，全部踢出去，你们代表的是CCF的形象。警告一次，教室再出现恶意刷屏，全部踢出去，你们代表的是CCF的形象。警告一次，教室再出现恶意刷屏，全部踢出去，你们代表的是CCF的形象。警告一次，教室再出现恶意刷屏，全部踢出去，你们代表的是CCF的形象。警告一次，教室再出现恶意刷屏，全部踢出去，你们代表的是CCF的形象。警告一次，教室再出现恶意刷屏，全部踢出去，你们代表的是CCF的形象。