题解

思路

从节点 $x$ 不断走向父亲，会依次删除当前最小质因子。因此从根到 $x$ 的边标签恰是 $x$ 的全部质因子按不升顺序排列。令 $S_k$ 表示 $k!$ 的这条质因子序列，其长度

$$d_k=\sum_{t=2}^{k}\Omega(t).$$

两个阶乘节点的 LCA 深度就是 $S_a,S_b$ 的最长公共前缀长度。

设 $a<b$，令 $q$ 为区间 $[a+1,b]$ 中出现的最大质因子。$b!$ 相比 $a!$ 第一个发生次数变化的质数就是 $q$，故

$$\operatorname{depth}(\operatorname{LCA}(a!,b!)) =\sum_{p\ge q}v_p(a!).$$

右侧可用质数表和 Legendre 公式计算；区间最大质因子可用 RMQ 查询。

压缩字典树

序列 $S_2,S_3,\ldots,S_{5000}$ 按字典序递增。只保留输入中出现的阶乘节点，将这些序列及相邻序列的 LCA 建成压缩字典树。用栈维护上一条根到叶路径，每次根据相邻 LCP 深度弹栈、必要时插入一个虚 LCA，再接入当前节点。节点数不超过出现的不同阶乘数的两倍。

对树中一条边，设删边后下方连通块包含 $s$ 个关键节点，总数为 $n$。选定点后，这条边对距离和的贡献是某一侧的关键节点数。树的中位点能同时令每条边取较小一侧，因此最小总距离为

$$\sum_{e}\operatorname{len}(e)\min(s_e,n-s_e).$$

做法

子任务 1：枚举候选节点

显式建立所有质因子路径，对每个树节点分别计算它到全部关键节点的距离并取最小值。

子任务 2：显式字典树

对每个出现的 $k!$ 生成完整质因子序列并插入字典树，再用子树计数公式求和。

子任务 3：相邻 LCP 压缩树

使用上述 LCP 公式和栈，只构造关键节点与虚 LCA 组成的压缩树，再自底向上累加子树权值和边贡献。

正确性证明

引理 1

根到 $k!$ 的路径标签为 $k!$ 的质因子按不升序排列。

证明。 向父亲移动每次删除当前最小质因子；逆向观察即按从大到小的次序加入质因子。$\square$

引理 2

对 $a<b$，相邻路径的 LCP 深度为 $\sum_{p\ge q}v_p(a!)$，其中 $q$ 是 $a+1,\ldots,b$ 中的最大质因子。

证明。 大于 $q$ 的质因子次数完全相同；质因子 $q$ 在 $b!$ 中首次增加。两条降序序列先共享 $a!$ 中所有不小于 $q$ 的因子，随后一条仍为 $q$，另一条进入更小质数或结束，因此恰在此处分叉。$\square$

引理 3

压缩树保留任意两个关键节点间的距离。

证明。 栈算法保留所有关键节点及相邻字典序节点的 LCA；这些节点包含关键点集合虚树所需的全部分叉点。压缩边长度取原树深度差，所以路径长度不变。$\square$

定理

算法输出所求最小距离和。

证明。 由引理 3，可在压缩树上等价求解。任意边的最优贡献下界为边长乘两侧关键点数较小值；树中位点使每个相邻分量权值不超过 $n/2$，同时达到所有边的下界。自底向上的公式恰好求出其总和。$\square$

复杂度

设 $K=5000$，不同关键阶乘数为 $u$。预处理为 $O(K\log K)$，LCP 查询总计 $O(u\pi(K)\log K)$，建树与统计为 $O(u)$；空间复杂度为 $O(K+u)$。