首先进行 top cluster 树分块。考虑这样一件事，对于两个簇的底部界点 (u,v)，我们把两个点都在 u,Fa_u;v,Fa_v 界点路径上的询问全都拉出来一起做，那么每次变化量肯定不会超过 4\sqrt{n}。
接下来要解决的只剩 (u,v) 转移到下一个 (u,v) 的代价和了，我们考虑抛出以下做法。
设 siz_u 为子树内界点个数和。对于 (u,v)，设 u 子树内界点 siz 最大的为 x，v 子树中的为 y，若 siz_u-siz_x<siz_v-siz_y 则 (u,v) 从 (x,v) 转移过来，否则从 (u,y) 转移过来。
这样子状态之间转移构成了一个大小为 n 的森林，在每棵树上遍历一遍即可。我们声称这样做时间复杂度是 O(n\sqrt{n}) 的。
这是因为在 n 个点的树上轻子树大小和 \geq x 的点的个数是 \frac{n}{x} 级别的，因为考虑在叶子处挂上这些 x 合并上来，只会合并叶子个数 -1 次。
那么考虑枚举 x 算贡献，一对 (u,v) 在 x 有贡献当且仅当轻子树大小和的 min 大于等于 x，那么对于 x 来说，可能产生贡献的界点点对数量最多为 (\frac{\sqrt{n}}{x})^2。那么答案的级别算一下就是 \sum_{x=1}^{\sqrt{n}} \frac{n\sqrt{n}}{x^2}\rightarrow n\sqrt{n}。