超级大好题，每一个部分的实现都很有难度，环环相扣，精彩绝伦。
考虑我们显然不能把 \(O(n^2)\) 的路径们全部列出来排序（我还真这么想过），因此往随机二分的方向想。问题转化成算长度 \(\le\) 当前枚举的长度的路径数，以及随机生成一个长度 \(\in [l,r]\) 的路径。
考虑建立点分树。对于每个子树，我们建一个记录该子树中，所有点按照到子树根距离从小到大排序的数组。这样，一个点在该子树中距离为 \([l,r]\) 的点就都在一个区间 \([L,R]\) 内。同时这个区间内除了到该点距离为 \([l,r]\) 的点以外，只剩下和该点在该子树根节点的同一个儿子子树内的点了。我们用 FHQ-Treap 维护即可。由于 \([L,R]\) 的两个指针都单调递减，所以可以双指针（不过按照指针数量，应该叫三指针）。
这个数组该怎么构建呢？考虑主席树。在本问题中，每个数都能看做一个不会进位的 \(n\) 进制数。因此，我们记录一条路径在 \(n\) 进制下每一位的值，即可通过 \(hash+\) 主席树上二分进行比大小。最棒的是，假如要将 \((rt,x),(rt,y)\) 两条路径合并，那么每一个 \(hash\) 值只需要相加即可，这大大减小了维护难度。构建时间复杂度 \(O(n\log^3n)\)。这个构建显然可以预处理。
构建好这个数组后，其余的内容只需要用 FHQ-Treap + 三指针即可解决，\(check\) 函数时间复杂度 \(O(n\log^2n)\)，加上随机二分，总时间复杂度为炒大肠 \(O(n\log^3n)\)。
还没敲完。