真神。
题意
给出一个 $n (n \le 10^5)$ 个点的带权树（边权 $w_i \le 10^6$），以及 $q(q \le 100)$ 个修改边的操作，输出每次修改边后以及所有修改之前，树上满足最短路径边权值 $\gcd$ 是 $1$ 的无序点对数。
思路
首先考察莫比乌斯函数的容斥含义。这可以由 $\gcd = 1$ 想到。如下式： \(\sum_{d \backslash \! \gcd} \mu(d) = [\gcd = 1]\) 不妨先考虑不带修改的情况。
对于每个边权，在剔除了平方因子后，最多由 $7$ 个质因数构成（这可以由 $2 \times 3 \times 5 \times 7 \times 11 \times 13 \times 17 = 510510$ 得知，再乘上 $19$ 后就超过了 $10^6$ 的范围）。于是可以枚举 $1 \sim 10^6$ 之内每个数字，并考察每条边是否包含它作为因子。由于每个边最多被算 $2^7$ 次，这一步的复杂度是可以接受的。
枚举质数，是为了计算贡献。对于每个因子 $p$，构建一个森林，每条新森林中的边满足 $p \backslash w_i$ ，这样的话森林的每棵树对答案的贡献就是 $\mu(p) \sum_{u \neq v} 1 = \sum_{u \neq v} \mu(p)= \mu(p) \times\frac{sz(sz-1)}{2}$ .
考虑修改。由于修改次数很少，可以暴力一点。用带撤销的并查集维护。我们不妨首先把询问离线并且忽略所有被改过的边，求一次答案。考虑删掉一条边和加上一条边后，答案怎么变化。
- 删掉一条边。对于每个质数因子，损失的答案是 $\mu(p) \times sz_l \cdot sz_r$ .
- 加上一条边。对于每个质数因子，增加的答案是 $\mu(p) \times sz_l \cdot sz_r$ .
然后用并查集同时维护连通性即可。
