[雅礼集训]Tree

Posted by Panda2134's Blog on May 3, 2018

真神。

题意

给出一个 $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$ .

然后用并查集同时维护连通性即可。