GPT 5.6 Pro 只能做到 $\widetilde O(n^{5/4} \sqrt{\log n})$？玩的太差了！下面给出的更精细上界是 $O(n^{9/8}+m+n^{1/2}m^{3/4})$，空间复杂度为 $O(n^{9/8}+m)$。

公开解题报告给出了 $O(n\sqrt{n+m})$ 的算法，另一个公开题解将其改进到了 $O(N^{5/4}\sqrt{\log N})$。这里继续消掉后者的 $\sqrt{\log N}$：保留换根、整链压缩和离线移动的结构，但用更多预处理空间，把其中的整链操作降到真正的 $O(1)$，而不是把线段树的对数因子忽略掉。以下讨论采用通常的 word-RAM 模型，给出的是可证明的算法上界，不声称已经有匹配的最优性下界。([QOJ][1])

一、把排名询问归约为两条根路径之间的逆序对

题目中的产物包含所有后代的产物，并按降序排列后的字典序比较；排名采用“严格大于它的产物数量加一”，相同产物必须并列。([QOJ][2])

首先可以把产物比较等价地改成：比较所有直接孩子的产物构成的降序序列。证明方法是从大到小抵消相同的孩子产物。一个孩子的产物确定了其所有后代产物的多重集，因此相同孩子对应的贡献可以整体抵消；最大的不同孩子产物，又严格大于较小孩子的所有后代产物，故决定最终比较结果。这也是公开解题报告使用的第一个归约。([QOJ][1])

于是，产物可以用有根树的规范类型表示。记类型编号为 $w_u$，编号越大，产物越大。由比较定义归纳可知，高度较大的类型一定较大。因此可以按高度递增处理每一层，将孩子类型的降序序列排序、去重，得到确定性的类型编号。所有孩子序列的总长度为 $n-1$，用有序字典建立这些序列的字典树，可以在 $O(n\log n)$ 时间内完成，不需要随机哈希。

接下来选取一个特殊的固定根 $o$。若树只有一个直径中心，就选它；若有两个中心，断开中心边，比较两侧分别以中心为根的类型，选择类型较大的一侧作为 $o$。两侧类型可以先对这个森林统一编号后比较。

这样选根后，对 $o$ 的每个孩子 $c$，删去 $oc$ 后的根侧类型，都不小于 $c$ 侧类型。单中心时由高度得到严格不等式；双中心时只有中心边需要实际比较类型。

以下深度、祖先关系均相对于 $o$，令 $d_o=0$、$P_x=\operatorname{path}(o,x)$，并令 $\rho_y=1+\#{v:w_v>w_y}$。

将根改为 $x$ 后，$P_x$ 上的点按 $x\to o$ 的顺序排在最前面，路径外的点保持原类型顺序。原因是：设 $c$ 是 $o\to x$ 的第一个孩子，换根后的 $o$ 已经严格大于所有路径外产物，而沿路径向 $x$ 走，产物继续严格增大。因此：

$$ f(x,y)= \begin{cases} d_x-d_y+1,&y\in P_x,\\ \rho_y+\#\{v\in P_x:w_v\le w_y\},&y\notin P_x. \end{cases} $$

这个特殊根和排名公式，是公开解题报告中换根归约的核心。注意第二行使用的是 $w_v\le w_y$，不能写成严格小于。([QOJ][1])

对一次询问，记 $l=\operatorname{LCA}(s,t)$，将路径拆成 $\mathcal A=(l,s]$ 和 $\mathcal B=(l,t]$，长度分别为 $S,T$。两条臂上的点都按从 $l$ 向下的顺序编号。

考虑跨臂的有序对，令根为 $\mathcal A$ 上第 $i$ 个点，目标为 $\mathcal B$ 上的 $b_j$。设 $p_j=\#{u\in\mathcal A:w_u>w_{b_j}}$，由排名公式得到 $f(a_i,b_j)=\rho_{b_j}+\max(0,i-p_j)$。

所以，只有 $\rho_{b_j}\le r$ 的目标可能贡献答案，其贡献为 $\min(S,p_j+r-\rho_{b_j})$。记 $q$ 为满足 $\rho_{b_j}\le r$ 的前缀长度，$q_0$ 为满足 $f(s,b_j)\le r$ 的前缀长度。前 $q_0$ 个目标接受所有 $S$ 个根，其余目标的贡献没有触及上界 $S$，故：

$$ 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. $$

前三项可以直接计算或使用树上前缀和。最后一项才是真正需要处理的路径逆序对。

定义 $J(u,v)=\#{(a,b):a\in P_u,\ b\in P_v,\ w_a>w_b}$，并约定 $b_0=l$。由于 $P_l$ 上所有点的类型，都严格大于 $(b_{q_0},b_q]$ 上的类型，有 $\sum_{j=q_0+1}^{q}p_j=J(s,b_q)-J(s,b_{q_0})-(d_l+1)(q-q_0)$。

两个方向分别计算，一次原询问最多产生四个 $J$ 询问。

这里把其他贡献也集中写清楚。设两条臂上满足 $\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)=k(k+3)/2+(L-k)r$。当 $o_x=o_y=1$ 时，答案为 $1+H(S,r)+H(T,r)+a(a+1)/2+b(b+1)/2+C(\mathcal A,\mathcal B)+C(\mathcal B,\mathcal A)$。

其中 $H$ 统计目标是根的祖先的情况，两个三角形项统计根是目标的真祖先的情况，最后两项统计跨臂情况。

其余三类不需要 $J$。$(0,0)$ 直接使用排名公式；$(0,1)$ 的答案是 $\min(r,S+1)+q_0$。对于 $(1,0)$，若 $T=0$，答案是 $\min(r,S+1)$；否则，若 $\rho_t>r$，答案为 $1$；若 $\rho_t\le r$，令 $p=\#{u\in\mathcal A:w_u>w_t}$，答案为 $1+T+\min(S,p+r-\rho_t)$。

还需要快速找到上述边界。沿根路径，类型严格递减，因此类型阈值可以转换为祖先位置。对于 $q_0$，令 $k_s=|P_s|$：若 $r\le k_s$，则 $q_0=0$；否则，从全局类型多重集中删除 $P_s$ 上的类型，取剩余多重集的第 $r-k_s$ 大类型 $\tau$，目标合法当且仅当 $w_y\ge\tau$。阈值处所有相同类型都要保留，不能只保留恰好若干个点。([QOJ][3])

下面会同时支持这些边界查询，并将其做到 $O(1)$。

二、把整条最大孩子链的操作降到真正的 $O(1)$

把每个点连向类型最大的孩子，得到若干条最大孩子链。沿这种链向下，高度每次恰好减少一。

再建立一棵“类型树”：每种非叶类型 $t$ 的父亲，是它最大的孩子类型。叶类型作为根，那么类型 $t$ 在类型树上的深度正好等于其高度。

将类型树每个点的孩子按类型编号递增排列，求 DFS 区间 $[\operatorname{in}(t),\operatorname{out}(t)]$。同一深度上的类型，其 DFS 顺序恰好就是类型大小顺序：比较两个类型时先比较最大的孩子，只有最大孩子相同时才比较后续部分，正好对应“先比较父亲，再比较兄弟次序”。

考虑一段最大孩子链 $C$，顶部为 $c$，高度范围为 $[a,b]$，令 $k=\operatorname{in}(w_c)$。对于高度在 $[a,b]$ 内的点 $v$，链中同高度的类型就是 $w_c$ 在类型树中的对应祖先。因此，同高度时，链中类型大于 $w_v$，当且仅当 $\operatorname{out}(w_v)

于是，令 $I(C,P_z)$ 表示链中类型严格大于根路径中类型的点对数，就有：

$$ I(C,P_z) = |C|\cdot\#\{v\in P_z:h_v < a\} +\sum_{\substack{v\in P_z\\a\le h_v\le b}}(b-h_v) +\#\{v\in P_z:a\le h_v\le b,\ \operatorname{out}(w_v)< k\}. $$

反向的 $I(P_z,C)$ 也同样容易：高度大于 $b$ 的点贡献 $|C|$；高度在 $[a,b]$ 内的点贡献 $h_v-a+[\operatorname{in}(w_v)>k]$。

这些计数看似包含高度和 DFS 序两个维度，但根路径上的高度严格递减。因此，满足 $a\le h_v\le b$ 的点形成一段祖先链。先找出两个边界，随后只需在这段祖先链上，对 $\operatorname{in}$ 或 $\operatorname{out}$ 做一维前缀计数。高度和则用原树上的前缀和维护。

用普通可持久化线段树，这一步是 $O(\log n)$。要消掉最终的 $\sqrt{\log n}$，必须认真消掉这里的对数。

取 $\beta=\lceil(n+1)^{1/16}\rceil$，将 $[0,n]$ 内的整数写成固定 $16$ 位的 $\beta$ 进制数。建立可持久化 $\beta$ 叉计数树，每个结点保存所有孩子指针及孩子计数的前缀和。

一次更新只经过 $16$ 层；每层复制 $O(\beta)$ 个字段。因此，一次版本更新是 $O(\beta)$，而查询“小于某个键的元素个数”只需经过 $16$ 层，时间为真正的 $O(1)$。沿原树建立高度、类型、类型 DFS 进入时间、退出时间的根路径版本，就能支持上述计数。

祖先边界也能常数时间找到。给字典结点补充每个孩子之后的第一个非空孩子，以及最小键、最大键，即可在固定层数内查询后继。根路径上每种高度、每种类型至多出现一次，后继对应的原树结点，就是所需的祖先。

还剩下删除根路径后的第 $k$ 大类型。这里不能扫描 $\beta$ 个孩子，否则又会产生非常数的查询时间。处理方法是：在每个计数树结点内部，再为其前缀计数建立一个静态后继字典。

这个小字典只有至多 $\beta$ 个键，键是前缀出现次数，范围仍在 $[0,n]$。同样使用固定 $16$ 层的 $\beta$ 叉字典，它有 $O(\beta)$ 个结点，每个结点使用 $O(\beta)$ 空间，故可以在 $O(\beta^2)$ 时间、空间内建立，并支持 $O(1)$ 后继查询。重复的前缀计数保留最小孩子下标。

求第 $k$ 小时，查询第一个不小于 $k$ 的前缀计数，即确定应进入的孩子；减掉之前孩子的元素数后继续。外层和内层深度都固定，整个第 $k$ 小查询也是 $O(1)$。

从全局多重集开始，沿原树每深入一个点，就持久化删除该点的类型，得到所有“全局多重集减根路径”的版本。每次复制外层结点时，重建其小型后继字典，所有预处理的时间、空间均为 $O(n\beta^2)=O(n^{9/8})$。

因此，这个数据结构没有把线段树查询无故当成常数，而是用更贵的版本更新换取常数时间查询。至此，排名、类型阈值、祖先边界、整链与根路径的双向逆序对，都支持 $O(1)$。原树 LCA 用 Euler 序加稀疏表，预处理 $O(n\log n)$、查询 $O(1)$，其预处理同样被 $O(n^{9/8})$ 包含。

三、高度截断与离线移动

选取高度阈值 $B$，保留所有 $h_u\ge B$ 的点，得到高部分树。

高部分的每个叶子，其原树子树内都有至少 $B+1$ 个点。不同叶子的这些子树互不相交，所以高部分只有 $O(n/B)$ 个叶子。保留其根、叶子和分叉点，压缩其余只有一个高孩子的点，得到大小为 $K=O(n/B)$ 的骨架树。

骨架的一条边 $u\to v$ 对应原树中的 $(u,v]$。它是一段最大孩子链：链内部每个点只有一个高孩子，而其他孩子高度小于 $B$，所以这个高孩子必然是类型最大的孩子。这里必须排除上端点 $u$，因为从分叉点出发的第一步不一定走向最大孩子。

对任意点 $x$，设 $x_H$ 是最深的高祖先，$a_x$ 是 $P_{x_H}$ 上最深的骨架点，并令 $C_x=(a_x,x_H]$、$L_x=(x_H,x]$。那么 $P_x$ 被拆成骨架根路径 $P_{a_x}$、一段最大孩子链 $C_x$ 和短尾 $L_x$。短尾上的高度都小于 $B$，所以 $|L_x|\le B$。

由于高点的类型一定大于低点，展开点对后得到：

$$ \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} $$

两个整链项都是 $O(1)$。两条短尾上的类型分别单调，双指针即可在 $O(B)$ 时间内求逆序对。因此，每个 $J(x,y)$ 花费 $O(B)$ 时间，就能转化成一个骨架端点之间的询问。

若高部分为空，所有根路径长度都不超过 $B$，直接处理两条短尾即可。

现在只剩 $Q=O(m)$ 个骨架询问。对骨架树做包含回退的 Euler 游走，相邻位置对应父子点。维护当前两个位置 $u,v$ 和 $Z=J(u,v)$。

移动第一个位置时，根路径增加或删除一段最大孩子链 $C$，于是给 $Z$ 加减 $I(C,P_v)$；移动第二个位置时，加减 $I(P_u,C)$。每次移动均为 $O(1)$，与被压缩链的原始长度无关。

对两个 Euler 坐标使用二维莫队顺序，第一维块长取约 $K/\sqrt Q$，不足 $1$ 时取 $1$。总移动次数为 $O(K\sqrt Q+Q)$。排序键都是 $O(K)$ 范围内的整数，用两次稳定计数排序即可，不需要再引入比较排序的对数。

于是总时间为：

$$ O\!\left(n^{9/8}+mB+\frac{n\sqrt m}{B}+m\right). $$

取 $B=\max(1,\lceil\sqrt n,m^{-1/4}\rceil)$，得到 $O(n^{9/8}+m+\sqrt n,m^{3/4})$ 时间、$O(n^{9/8}+m)$ 空间。当 $n,m$ 同阶时，便是 $O(N^{5/4})$ 时间。所有点对数量及前缀和都应使用 $64$ 位整数。

这里真正减少复杂度的是两层结构：最大孩子链让长链可以整体处理，而高分支度的持久化字典用多项式预处理空间消掉整链操作的对数。它的实际常数会比二叉线段树版本更大，但最坏时间复杂度确实少了 $\sqrt{\log N}$，不是记号上的省略。