[NFLS 1462/4] 机房网络 题解

大意

给定一棵树, 有点权, 求两两间点权互质的点的距离之和.

题解

数论

考虑使用容斥.

设 $p_1, p_2, \cdots , p_k$ 为 $1 \to \max(a_i)$ 中的质数.

设 $P_x$ 为树中两个点间点权的 gcd 为 $x$ 的倍数的路径集合, $d(P)$ 为 $P$ 的所有路径的长度之和.

那么

$$\text{res} = d(P_1) - d(P_{p_1} \cup P_{p_2} \cup \cdots \cup P_{p_k}) = d(P_1) - d(P_{p_i}) + d(P_{p_i} \cap P_{p_j}) + d(P_{p_i} \cap P_{p_j} \cap P_{p_l}) \cdots = d(P_1) - d(P_{p_i}) + d(P_{p_i p_j}) - d(P_{p_i p_j p_l}) \cdots (i \not= j \not= l)$$

观察上式的系数以及 $P_x$ 中的 $x$ 可以发现, $x = 1$ 时, 系数为 $1$, $x$ 有一个因数时, 系数为 $-1$, 两个为 $1$, 三个为 $-1$, 同时不存在 $x$ 有两个及以上因数的项.

可以发现符合莫比乌斯函数的性质.

所以

$$\text{res} = \sum_{i = 1}^{\max(a_j)} \mu(i) \cdot d(P_i)$$

树论

现在要求 $d(P_x)$.

可以用树上启发式合并.

设 $dis_x$ 为当前记录的子树中, $x \mid val_v$ 的 $\sum_u dep_v$.

那么, 点 $u$ 的贡献为:

$$\sum_{y \mid val_u} \mu(i) \cdot (dis_x + dep_{u} - 2 \cdot dep_{lca})$$