套路地，对每个 \(g \in [1, n - 1]\) 求出有多少对无序对 \((u, v)\) 满足 \(g|f(u, v)\)，然后就可以用一个倒序枚举的 \(\mathcal O(n \log n)\) 的容斥求出答案。
考虑点分治，对每个经过分治中心 \(c\) 的 \(u \rightsquigarrow \text{lca}(u, v) \rightsquigarrow v\) 只需分两种情况讨论（为了方便表述，记 \(\mathcal T_u\) 表示以 \(u\) 为根的子树）：
-
\(u, v \in \mathcal T_c\)
此时显然 \(\text{lca}(u, v) = c\)，开个桶做一下就好。
具体地，维护 \(cnt_i = \sum\limits_{u \in \mathcal T_c}[d(c, u) = i], c_i = \sum\limits_{i | j}cnt_j\)，然后合并的时候枚举 \(g\) 统计贡献即可，单层时间复杂度是 \(\mathcal O(n \log n)\)。
-
\(u, v\) 一个在 \(\mathcal T_c\) 内，一个在 \(\mathcal T_c\) 外（可以钦定此时 \(u \in \mathcal T_c, v \notin \mathcal T_c\)）
同样是维护 \(cnt_i = \sum\limits_{u \in \mathcal T_c}[d(c, u) = i]\)，然后对从分治中心到当前子树的根节点路径上的点维护一个同样的桶 \(cnt'\)，合并时枚举 \(g\)，还要做在 \(cnt\) 上查询某个下标间隔为 \(g\) 的子序列和，记忆化一下就能做到单层 \(\mathcal O(n \sqrt n)\)。
关于时间复杂度的计算：记 \(H = \max\limits_{u \in \mathcal T_c}d(c, u)\)。对 \(g > \sqrt H\)，单次查询时间复杂度 \(\mathcal O(\sqrt H)\)；对 \(g \le \sqrt H\)，最劣（也就是完全没用到记忆化的规模最大）的情况下是对每个 \(g\) 恰好查询所有 \(g\) 个不同的子序列和，时间复杂度 \(\mathcal O(H \sqrt H)\)，查询次数 \(\mathcal O(H)\)，均摊时间复杂度 \(\mathcal O(\sqrt H)\)。总查询次数是 \(\mathcal O(n)\) 的，故时间复杂度为 \(\mathcal O(n \sqrt H)\)，也即单层 \(\mathcal O(n \sqrt n)\)。如果仔细算了时间复杂度，自然会发现常数非常小。
然后我们知道了单层时间复杂度是 \(\mathcal O(n \sqrt n)\)，点分治的时间复杂度是 \(\mathcal O(n \log n)\)，根据主定理，取大的单层时间复杂度，总体时间复杂度是 \(\mathcal O(n \sqrt n)\)。
代码：