首先如果从 x 走到 y 的过程中没有使用传送门，时间就是 x 和 y 的树上距离。如果使用了传送门，首先会从 x 开始沿着某条路径走到一个传送门，容易发现每个有传送门的点其实是等价的，于是可以设 f 为当前这个方案中，从某个传送门出发，期望多少时间到 y，直接写出转移式子得到 f=1+\frac{a\times f+b\times f+S}{n}，其中 a,b,S 分别表示有传送门的节点个数，没有传送门但沿着指定边走会到传送门的节点个数，所有没有传送门的节点到达传送门或终点所需时间总和，解一下这个式子得到 f=\frac{n+S}{n-a-b}。
然后可以发现那 b 个节点对 S 的贡献是完全没有必要的，因为把这些节点都放上传送门，分母不变，分子会变小，所以最优方案如果不是直接从 x 走到 y，那么所有没放传送门的节点构成以 y 为根节点的连通块，且 x 一定会放传送门，于是只需要求 \min_i\frac{n+\sum_{j=1}^il_j}{i}，其中 l 是以 y 为根后除 x 子树外所有节点的深度升序排序的结果（深度定义为节点到根节点的边数）。由于要求最小值考虑这个数组的差分 g_i=\frac{n+\sum_{j=1}^{i+1}l_j}{i+1}-\frac{n+\sum_{j=1}^{i}l_j}{i}=(i\times l_{i+1}-\sum_{j=1}^il_j-n)\times\frac{1}{i(i+1)}，发现前两项相当于是把 l 的点前 i 项都补成 l_{i+1} 所需的代价，所以可以发现这个差分数组为负的一定是前面某一段。
到这里看起来已经可以算了，但是还有个问题是需要把 x 子树剔除，否则 y 取的方案中 x 可能根本没放传送门，考虑不剔除会怎么样，设 x 在 l 序列中编号为 k，若前面那个最小值在前 k-1 项肯定就没啥问题，否则一定有 g_{k-1}\le0，也就是 l_k\le\frac{\sum_{j=1}^{k-1}l_j+n}{k-1}，然后发现这个式子就是在说取 k-1 个非传送门节点比直接走过去不优，并且这个式子类似于取个平均值，所以 k 以及后面的都是不会比直接走更优的。
于是问题转化成了对于每个 y 求出一个答案，每个询问再跟直接走的答案取 min。根据 g 正负性的性质可以直接二分，然后用点分树求与某个点距离不超过 t 的距离之和，复杂度 O(n\log^2n)，卡常的话可以把二分范围调成下面那个根号，应该是可以卡过的。
还可以做些观察，观察 g_i 的正负性容易发现当 1+\dots+l_{i+1}\ge n 时 g 一定是正的，于是就有了维护每个节点子树内不超过 O(\sqrt n) 的每个深度的节点个数再换根求答案的做法，时空复杂度均为 O(n\sqrt n)。本来 5\times10^5 说不定还能卡卡，但是这个东西的根号空间好像根本去不掉，于是拼个 B 性质 80 分。
进一步观察，考虑相邻两个节点，它们对应的 l 序列每个元素至多相差 1，再考虑一下 g 前两项值的意义，容易发现这两个点的 min 所取的深度差也不会超过 1，于是只用 O(n) 次领域深度和，复杂度 O(n\log n)。