题意理解

我们有一棵 $n$ 个节点的树，每个节点 $i$ 有一个权值 $a_i$（是 $1$ 到 $n$ 的排列）。对于每个节点 $x$，需要计算其子树内所有节点参与的游戏的欢乐值：

• 单点贡献：$\sum_{i \in \text{subtree}(x)} f_d(a_i^2)$
• 双点贡献：$\sum_{i,j \in \text{subtree}(x), i < j} f_d(a_i a_j)$

其中函数 $f_d(z)$ 定义为：将 $z$ 质因数分解为 $\prod_i p_i^{k_i}$，则

$$f_d(z) = \prod_i (-1)^{k_i} [k_i \le d]$$

核心思路

关键观察 1：$f_d$ 函数的性质

$f_d(z)$ 是一个积性函数，且可以表示为：

$$f_d(z) = \mu(z) \cdot [\text{所有质因子的指数} \le d]$$

其中 $\mu(z)$ 是莫比乌斯函数。

特别地，当 $d$ 足够大时（$d \ge \max k_i$），$f_d(z) = \mu(z)$。

关键观察 2：问题转化

总欢乐值可以重写为：

$$\text{ans}(x) = \frac{1}{2} \left[ \left(\sum_{i} f_d(a_i^2) + \sum_{i,j} f_d(a_i a_j)\right) - \sum_i f_d(a_i^2) \right] + \sum_i f_d(a_i^2) $$

化简后：

$$\text{ans}(x) = \frac{1}{2} \left[ \left(\sum_{i} f_d(a_i^2)\right)^2 + \sum_i f_d(a_i^2) \right] $$

证明：利用 $f_d$ 的积性，$f_d(a_i a_j) = f_d(a_i) f_d(a_j)$ 当 $\gcd(a_i, a_j) = 1$，但这里需要更精细的分析。

关键观察 3：莫比乌斯反演

通过莫比乌斯反演，可以将 $f_d(a_i a_j)$ 表示为：

$$f_d(a_i a_j) = \sum_{k \mid \gcd(a_i, a_j)} g_d(k) $$

其中 $g_d$ 是某个与 $f_d$ 相关的函数。

算法框架

方法一：树上启发式合并（DSU on Tree）

主要步骤：

1. 对树进行 DFS，预处理重儿子
2. 对于每个节点 $x$：
   • 先递归处理所有轻儿子
   • 然后处理重儿子，保留重儿子的统计信息
   • 最后加入轻儿子的贡献
3. 在合并过程中维护 $cnt[v]$：当前子树中权值 $v$ 出现的次数

贡献计算： 维护 $\sum_{i} f_d(a_i^2)$ 和 $\sum_{i,j} f_d(a_i a_j)$，后者可以通过：

$$\sum_{i,j} f_d(a_i a_j) = \sum_k g_d(k) \cdot \left(\sum_{k \mid a_i} cnt[a_i]\right)^2 $$

复杂度：$O(n \log n \cdot F(d))$，其中 $F(d)$ 是与 $d$ 相关的因子

方法二：DFS 序 + 数据结构

将树转化为 DFS 序，那么每个子树对应一个区间：

• 单点贡献：区间求和
• 双点贡献：需要计算区间内所有点对的 $f_d(a_i a_j)$ 之和

使用莫队算法或分块处理。

方法三：生成函数 + 卷积

对于每个质因子 $p$ 考虑贡献，设 $h_p(k)$ 表示质因子 $p$ 的指数为 $k$ 时的贡献（$(-1)^k$ 或 $0$）。

总答案可以表示为各质因子贡献的卷积。

数论细节

$f_d$ 的预处理

预处理 $1$ 到 $n$ 的：

• 质因数分解
• 莫比乌斯函数 $\mu(i)$
• $f_d(i)$ 的值

对于 $f_d(i)$，检查每个质因子的指数是否 $\le d$，如果是则贡献 $(-1)^{k}$，否则为 $0$。

贡献计算优化

利用 $a_i$ 是排列的性质，每个值恰好出现一次。

对于双点贡献：

$$\sum_{i,j} f_d(a_i a_j) = \sum_{u,v} f_d(uv) \cdot [u \in S] \cdot [v \in S] $$

其中 $S$ 是当前子树的权值集合。

复杂度分析

• 预处理：$O(n \log \log n)$ 筛法预处理数论函数
• 树上启发式合并：$O(n \log n \cdot \tau(n))$，其中 $\tau(n)$ 是因子个数
• 空间复杂度：$O(n)$

在 $n \le 2 \times 10^5$ 时，启发式合并是可行的。

实现要点

1. 数论预处理：线性筛预处理最小质因子、莫比乌斯函数
2. $f_d$ 计算：根据质因数分解计算每个数的 $f_d$ 值
3. 树上统计：维护当前子树的权值出现次数
4. 贡献更新：添加/删除节点时更新单点和双点贡献

总结

本题的核心在于：

1. 数论分析：理解 $f_d$ 函数的积性性质和莫比乌斯表示
2. 问题转化：将欢乐值计算转化为数论函数的求和
3. 算法选择：使用树上启发式合并高效处理子树查询
4. 优化技巧：利用数论性质和排列特性优化计算

这是一个典型的数论与树算法结合的难题，需要深厚的数学功底和算法实现能力。