官方题解只能做到 $\widetilde O(N^{1.5})$？玩的太差了。这题可以做得比平方根分块更快。下面给出一套确定性的离线算法，时间复杂度为
$$ \boxed{ O\!\left((n+m)\log n+\sqrt n\,m^{3/4}\sqrt{\log n}\right) } $$
空间复杂度为
$$ \boxed{O(n\log n+m)}. $$
当 $n,m$ 同阶，记为 $N$ 时，时间复杂度是
$$ \boxed{O\!\left(N^{5/4}\sqrt{\log N}\right)}. $$
作为对照，QOJ 上公开的解题报告最终给出的复杂度是 $O(n\sqrt{n+m})$，在 $n,m$ 同阶时为 $O(N^{3/2})$。下面的改进不是调整分块参数，而是利用产物比较规则，把长链压缩后的操作也做快。([QOJ][1])
完整 C++17 实现在文末。先说明：这里证明的是上述算法的上界，不是声称已经证明了这道题的理论最优复杂度。
一、先把递归的“所有后代”改成“直接孩子”
题目中的产物包含的是所有后代的产物，而不只是孩子；比较时则把元素降序排列，比较字典序。
但对于比较大小而言，可以等价地改成：
$$ T_u=\operatorname{sort}_{\downarrow}\{T_v:v\text{ 是 }u\text{ 的孩子}\}. $$
这里需要证明，不能直接替换定义。
考虑两棵树的孩子产物多重集。从大到小抵消相同的孩子产物，设最大的不同产物为 $A$。
相同的孩子产物，其包含的所有后代产物也完全相同，可以一并抵消。而比 $A$ 小的孩子，其后代产物都比该孩子更小，因此不可能影响 $A$ 这一位置的比较。于是，比较所有后代与比较直接孩子，得到的结果相同。
另外，由递归定义可以归纳得到：
$$ h(T_1)>h(T_2)\Longrightarrow T_1>T_2, $$
其中 $h(T)$ 是树高，叶子的高度为 $0$。
因此，固定根后，可以给所有子树分配规范类型编号 $w_u$，满足
$$ w_u< w_v\iff T_u< T_v,\qquad w_u=w_v\iff T_u=T_v. $$
如何确定性地在 $O(n\log n)$ 内编号？
按高度从小到大处理。
对于当前高度的每个结点，构造其孩子类型编号的降序序列，然后将这些序列按字典序排序、去重。
所有孩子序列的总长度为 $n-1$。使用归并排序比较序列，每一层归并的字符比较次数，可以摊到该层被输出的序列长度上。因此总复杂度为 $O(n\log n)$，不需要随机哈希。
二、选择一个特殊根：换根相当于把一条路径移到最前面
这是整个问题最重要的结构性质。
2.1 特殊根怎么选？
先求树的直径中心。
如果只有一个中心，就选它。
如果有两个相邻中心 $c_1,c_2$，删去中间的边，比较两侧分别以 $c_1,c_2$ 为根的产物。选择产物较大的一侧的端点作为根；相等时任选。
记选出的根为 $o$，之后所有父子关系、深度和子树，都相对于 $o$。
对 $o$ 的任意孩子 $c$，都有：
$$ T(o\mid c)\ge T_c, $$
其中 $T(o\mid c)$ 表示删去 $oc$ 后，包含 $o$ 的一侧以 $o$ 为根的产物。
单中心时，这个关系由高度严格比较得到；双中心时，只有中心边需要比较实际产物，其他边仍可直接用高度判断。
2.2 换根后的排序
定义
$$ P_x=\operatorname{path}(o,x). $$
定理：以 $x$ 为根时，所有结点按产物降序排列，等价于：
- 首先按 $x\to o$ 的顺序排列 $P_x$ 上的所有结点。
- 剩下的结点，仍然按固定根 $o$ 下的 $w$ 从大到小排列。
路径上的产物严格递减，且严格大于路径外的所有产物。
证明如下。设 $c$ 是 $o\to x$ 路径上的第一个孩子。换根后，$o$ 的产物变成 $T(o\mid c)$。
对于路径外的结点：
- 在 $c$ 子树外的结点，都是这个产物对应树的真后代。
- 在 $c$ 子树内的结点，是真正位于 $c$ 以下的结点，其产物小于 $T_c\le T(o\mid c)$。
所以换根后 $o$ 的产物已经大于所有路径外产物。沿路径向新根 $x$ 走，产物又严格变大，定理得证。
2.3 排名公式
记
$$ d_u=\operatorname{dep}(u),\qquad \rho_u=1+\#\{v:w_v>w_u\}. $$
注意 $\rho_u$ 是按严格大于计数的排名，同类产物并列，不能把并列名次拆开。题目本身采用的也是这个排名定义。
于是：
$$ \boxed{ f(x,y)= \begin{cases} d_x-d_y+1,&y\in P_x,\\[2mm] \rho_y+\#\{z\in P_x:w_z\le w_y\},&y\notin P_x. \end{cases} } $$
根路径上的 $w$ 严格递减，所以后面的计数可以用倍增在 $O(\log n)$ 内完成。
三、所有询问都能归约成常数个“根路径之间的逆序对”
题目的四类询问分别让 $X,Y$ 取端点或整条路径。
先解决两个边界查找问题，再讨论最难的 $(o_x,o_y)=(1,1)$。
3.1 不要对排名函数做两层二分
固定根 $x$，设
$$ k_x=|P_x|=d_x+1. $$
根据换根排序定理：
如果 $r\le k_x$，只有 $x\to o$ 路径上的前 $r$ 个结点合法，路径外没有合法结点。
如果 $r>k_x$，先从全部结点的类型多重集中，删去 $P_x$ 上每个结点对应的一份类型。设剩余多重集的第 $r-k_x$ 大类型为 $\tau$，那么路径外结点合法当且仅当
$$ w_y\ge \tau. $$
这可以用“全局频率减根路径可持久化线段树”，在 $O(\log n)$ 内求出。
这里取的是类型阈值，不是恰好取若干个结点。 阈值处的所有并列产物都要保留。
随后沿一条祖先链找最深的 $w_y\ge\tau$ 的结点，再做一次倍增即可。因此整个边界查找是 $O(\log n)$，不需要 $O(\log^2 n)$。
3.2 将询问路径分成两条臂
令
$$ l=\operatorname{LCA}(s,t), $$
并记
$$ \mathcal A=(l,s],\qquad \mathcal B=(l,t], $$
长度分别为 $S,T$。两条臂都按从 $l$ 向下的顺序编号。
考虑跨臂的有序对：
$$ x\in\mathcal A,\qquad y=b_j\in\mathcal B. $$
定义
$$ p_j=\#\{u\in\mathcal A:w_u>w_{b_j}\}. $$
因为 $\mathcal A$ 上的类型严格递减，如果 $x$ 是这条臂上的第 $i$ 个结点，那么
$$ f(x,b_j)=\rho_{b_j}+\max(0,i-p_j). $$
所以，当 $\rho_{b_j}\le r$ 时，这个 $y$ 对答案的贡献为
$$ \min\bigl(S,p_j+r-\rho_{b_j}\bigr); $$
否则贡献为 $0$。
设：
- $q$ 是 $\mathcal B$ 上满足 $\rho_y\le r$ 的前缀长度；
- $q_0$ 是 $\mathcal B$ 上满足 $f(s,y)\le r$ 的前缀长度。
前者可以沿祖先链倍增查找，后者使用上一节的可持久化第 $k$ 大查找。均为 $O(\log n)$。
前 $q_0$ 个目标能接受 $\mathcal A$ 上的所有根；接下来的目标不会触及贡献上界 $S$。因此跨臂贡献为
$$ \boxed{ C(\mathcal A,\mathcal B) = Sq_0+(q-q_0)r -\sum_{j=q_0+1}^{q}\rho_{b_j} +\sum_{j=q_0+1}^{q}p_j. } $$
前三项可以直接计算或用树上前缀和计算。
唯一困难的是最后一项：
$$ \sum_{j=q_0+1}^{q}p_j = \#\{(x,y):x\in\mathcal A,\ y\in(b_{q_0},b_q],\ w_x>w_y\}. $$
也就是两条祖先链之间的严格逆序对。
3.3 进一步只保留根路径询问
定义核心询问
$$ J(u,v)= \#\{(x,y):x\in P_u,\ y\in P_v,\ w_x>w_y\}. $$
设 $u=b_q,\ v=b_{q_0}$，约定 $b_0=l$。则
$$ \boxed{ I(\mathcal A,(v,u]) = J(s,u)-J(s,v)-|P_l|(d_u-d_v). } $$
最后减去的部分成立，是因为 $P_l$ 上的所有产物都严格大于 $(v,u]$ 上的产物。
因此，一个方向的跨臂贡献只需要两个 $J$；两个方向总共最多四个。原问题被归约成了
$$ Q=O(m) $$
个根路径逆序对询问。
3.4 同臂贡献与其余询问
设两条臂上满足 $\rho_y\le r$ 的前缀长度为 $a,b$。定义
$$ H(L,r)=\sum_{i=1}^{L}\min(r,i+1). $$
令 $k=\min(L,r-1)$，则
$$ H(L,r)=\frac{k(k+3)}2+(L-k)r. $$
完整的双路径答案为
$$ \boxed{ \begin{aligned} \operatorname{ans} ={}&1+H(S,r)+H(T,r)\\ &+\frac{a(a+1)}2+\frac{b(b+1)}2\\ &+C(\mathcal A,\mathcal B)+C(\mathcal B,\mathcal A). \end{aligned} } $$
这里，$H$ 统计目标是根的祖先的情况，两个三角形项统计根是目标的真祖先的情况。
其余三类询问不需要 $J$：
$(0,0)$：直接使用排名公式。
$(0,1)$：答案为
$$ \min(r,S+1)+q_0, $$
其中 $q_0$ 是 $\mathcal B$ 上满足 $f(s,y)\le r$ 的前缀长度。
$(1,0)$：如果 $T=0$，答案为 $\min(r,S+1)$。否则，如果 $\rho_t>r$，只有 $x=t$ 合法，答案为 $1$；如果 $\rho_t\le r$，令
$$ p=\#\{u\in\mathcal A:w_u>w_t\}, $$
答案为
$$ 1+T+\min(S,p+r-\rho_t). $$
所以，除去 $J$ 之外，每个原询问只需要 $O(\log n)$ 时间。
四、真正的加速点：一整条“最大孩子链”可以一次加入
现在考虑如何批量处理 $J(u,v)$。
直接移动根路径端点，每次加入或删除一个结点，仍然容易落入平方根复杂度。我们需要做到：
一次加入或删除一整条长链，与另一条根路径之间的逆序对仍能在 $O(\log n)$ 内计算。
这里的长链必须沿着产物最大的孩子走，不能是任意长链。
4.1 构造另一棵树：类型树
对于每一种非叶类型 $t$，定义
$$ \operatorname{parentType}(t) = \text{该类型最大的孩子类型}. $$
把所有不同类型按这个关系连接起来，得到一棵以叶类型为根的树，称为类型树。
它至多有 $n$ 个结点，并且：
$$ \operatorname{depth}_{\text{类型树}}(t)=h(t). $$
将类型树上同一个父亲的孩子按类型大小递增排列，再进行 DFS，记录
$$ \operatorname{in}(t),\operatorname{out}(t). $$
有一个关键性质：
类型树同一深度上的类型，其 DFS 先后顺序，恰好就是产物从小到大的顺序。
原因是比较两个非叶类型时，首先比较最大的孩子；只有最大孩子相同，才比较后续孩子。这正好对应类型树上“先比较父类型，再比较同父亲的孩子次序”。
4.2 沿最大孩子链，同高度类型可以用 DFS 区间比较
设一条最大孩子链 $C$ 的顶部为 $c$，链上高度范围为
$$ [a,b],\qquad b=h_c. $$
它在每个高度 $a,a+1,\ldots,b$ 上恰有一个结点。
这条链上高度为 $h$ 的类型，正好是类型 $T_c$ 在类型树中深度为 $h$ 的祖先。
设
$$ k=\operatorname{in}(T_c). $$
对于另一结点 $v$，当 $h_v\in[a,b]$ 时：
$$ \boxed{ T_{C(h_v)}>T_v \iff \operatorname{out}(T_v)< k. } $$
反向则为
$$ \boxed{ T_v>T_{C(h_v)} \iff \operatorname{in}(T_v)>k. } $$
如果 $k$ 落在 $T_v$ 的子树区间内，则两者类型相同，不计入严格逆序对。
4.3 链与根路径的逆序对公式
定义
$$ I(C,P_z)=\#\{(u,v):u\in C,\ v\in P_z,\ w_u>w_v\}. $$
对于固定的 $v\in P_z$，链中比它大的结点数为
$$ \begin{cases} b-a+1,&h_v< a,\\ b-h_v+[\operatorname{out}(T_v)< k],&a\le h_v\le b,\\ 0,&h_v>b. \end{cases} $$
因此，我们只需要查询：
- 高度小于 $a$ 的结点数；
- 高度在 $[a,b]$ 内的结点数、高度和；
- 这段中满足 $\operatorname{out}(T_v)< k$ 的结点数。
看起来像二维计数，但这里不需要二维数据结构：
根路径上的高度严格递减，所以高度在 $[a,b]$ 内的结点必然形成一段祖先链。用两次倍增找到它的端点，最后一个计数就变成了这段祖先链上的一维值域计数。
沿原树根路径，分别对类型树的 in、out 建可持久化线段树即可。
于是：
$$ \boxed{ I(C,P_z),\ I(P_z,C) \text{ 都可以在 }O(\log n)\text{ 内计算}. } $$
这一步是后面降低复杂度指数的基础。
五、按高度截断：高处只有 $O(n/B)$ 个需要保留的结点
选择一个高度阈值 $B\ge1$，保留所有满足
$$ h_u\ge B $$
的结点，得到高部分树 $T_B$。因为祖先高度更大，它是一个包含根的连通子树；也可能为空。
5.1 高部分的叶子很少
$T_B$ 的叶子恰好是原树中高度为 $B$ 的结点。
每个这样的结点下面，都有一条包含 $B+1$ 个结点的向下路径。不同高部分叶子的原树子树互不相交，所以
$$ \#\operatorname{leaf}(T_B)\le \frac{n}{B+1}. $$
只保留 $T_B$ 中的根、叶子和分叉结点，压缩其他只有一个高孩子的结点，得到骨架树。
它的结点数满足
$$ \boxed{K=O(n/B)}. $$
5.2 每条压缩边都对应一条最大孩子链
设一条压缩边从骨架结点 $u$ 连向 $v$。
将它对应的原树结点集合定义为
$$ (u,v], $$
即不包含上端分叉点 $u$。
这条链内部的每个结点只有一个高孩子。其他孩子高度小于 $B$，因此这个唯一高孩子一定是产物最大的孩子。
所以 $(u,v]$ 确实是一条最大孩子链，可以使用上一节的 $O(\log n)$ 整链操作。
排除上端分叉点是必要的：从分叉点出发的第一条边，不一定走向其最大孩子。
5.3 任意根路径只剩一条短尾和一条链
对于结点 $x$，令：
- $x_H$ 是它最深的高祖先；
- $a_x$ 是 $P_{x_H}$ 上最深的骨架结点；
- $C_x=(a_x,x_H]$；
- $L_x=(x_H,x]$。
于是有不交并：
$$ \boxed{ P_x=P_{a_x}\sqcup C_x\sqcup L_x. } $$
其中：
$$ |L_x|\le B, $$
因为 $L_x$ 的高度都小于 $B$，且沿路径严格下降。
$C_x$ 是至多一条最大孩子链。
因此
$$ \boxed{ \begin{aligned} J(x,y) ={}&J(a_x,a_y)\\ &+I(C_x,P_{y_H}) +I(P_{a_x},C_y)\\ &+|P_{x_H}|\cdot |L_y|\\ &+I(L_x,L_y). \end{aligned} } $$
解释一下两个交叉项：
高结点的产物一定大于低结点，所以“高 $x$、低 $y$”全部计入，“低 $x$、高 $y$”全部不计入。
最后两个短尾上的类型各自单调，用双指针归并即可在 $O(B)$ 内计算 $I(L_x,L_y)$。
所以，每个原来的 $J(x,y)$，只需花费
$$ O(B+\log n) $$
时间，就能转化为一个骨架端点之间的询问 $J(a_x,a_y)$。
六、骨架上的二维莫队：每移动一步，加入或删除整条链
现在只剩骨架结点之间的根路径逆序对询问。
对骨架树做包含回退过程的欧拉游走，长度为 $O(K)$。相邻两个位置对应的结点一定互为父子。
将询问 $J(a,b)$ 映射为两个端点在欧拉游走中首次出现的位置。
维护两个当前位置 $u,v$，以及
$$ Z=J(u,v). $$
移动第一个位置一步时，$P_u$ 会加入或删除一条压缩边对应的最大孩子链 $C$，于是
$$ Z\gets Z\pm I(C,P_v). $$
移动第二个位置一步时，
$$ Z\gets Z\pm I(P_u,C). $$
每次移动只需 $O(\log n)$，与压缩边的原始长度无关。
对这两个坐标进行二维莫队式排序。若有 $Q$ 个询问，第一维块长取约
$$ K/\sqrt Q, $$
总移动次数为
$$ O(K\sqrt Q+Q). $$
两个排序键都是 $O(K)$ 范围内的整数，可以用两次稳定计数排序，避免额外的比较排序复杂度。
因此骨架部分的时间复杂度为
$$ O\bigl((K\sqrt Q+Q)\log n\bigr). $$
代入 $K=O(n/B)$，就得到需要的改进。
七、总复杂度
前面的子树类型编号、倍增、可持久化线段树和原询问归约，总计
$$ O((n+m)\log n). $$
有 $Q=O(m)$ 个根路径逆序对询问。处理短尾的代价为
$$ O(mB), $$
处理骨架的代价为
$$ O\left(\frac nB\sqrt m\log n+m\log n\right). $$
因此
$$ \boxed{ T(B)= O\left( (n+m)\log n +mB +\frac nB\sqrt m\log n \right). } $$
平衡后两项：
$$ mB\asymp \frac nB\sqrt m\log n, $$
得到
$$ B\asymp \sqrt{\frac{n\log n}{\sqrt m}}. $$
最终：
$$ \boxed{ T= O\left( (n+m)\log n +\sqrt n\,m^{3/4}\sqrt{\log n} \right). } $$
当 $n=m=N$ 时：
$$ B\asymp N^{1/4}\sqrt{\log N}, \qquad \boxed{T=O(N^{5/4}\sqrt{\log N})}. $$
实际实现中，还可以枚举高度阈值，根据每个阈值对应的真实骨架大小选择代价较小的那个，而不是始终使用 $n/B$ 的最坏情况估计。下面的代码采用了这种选择方式。