给定一个 $n$ 个节点的树，每个点有一个正整数权值 $a_i$ 。我们定义 $g(x,y)$ 为 $x,y$ 之间简单路径上所有点（包括端点）的权值的最大公约数。
现在请求出对于所有的 $i \in [1,2×10^5]$ ，满足 $1 \le x \le y \le n$ 且 $g(x,y) = i$ 的点对 $(x,y)$ 的数目。
链接
题解
一个结论：一个数的约数个数不会很多。
在 $100000000$ 之内，约数最多的数是 $73513440$ ，有 $768$ 个因子。这大约不是 $log$ 级别的？令它是一个 $O(d(n))$ 级别的吧。
Solution A:
容斥原理：
所有以 $q$ 为最大公约数的点对的数目等于所有以 $q$ 为公约数的点对数目减去以 $2q,3q,…,kq$ 为最大公约数的点对数目。
所以我们采用逆序计算以 $q$ 为公约数的点对数目，就可以推出以 $q$ 为最大公约数的点对数目。
考虑怎么计算这个问题。如果两个点对的公约数是 $q$ ，那么他们路径上的所有边两端连的点的 $gcd$ 都是 $q$ 或者 $q$ 的倍数，经过的点的权值也一定是 $q$ 或者 $q$ 的倍数。因为权值不大，我们用权值记录点，用 $gcd$ 记录边。考虑到如果把所有的 $gcd$ 为 $q$ 或者 $q$ 的倍数的边全都连起来，这样图里所有联通的点都是满足条件的。所以我们只需要连边，然后维护点对数目。
我们维护一个并查集。记录集合大小。每次先将上述的点初始化，然后把边连上。用一个cnt维护所有联通点对数目，注意一个点也算点对。然后联通集合的时候加上从这端到那端的所有点对就可以了。
来分析一下复杂度。这里的复杂度主要集中在：并查集的初始化（满足条件的点）和并查集的合并（满足条件的边），每个操作都是 $O(1)$ 的，我们考虑一下它会被执行多少次。发现每个点都会被权值的因数初始化一次，所以这个是 $O(nd(n))$ 的。对于边的话也是一样，所以复杂度大约是 $O(n d(n))$ 的。
如果 $d(n)$ 不是很大，那么这个东西过掉问题不大。
Solution B:
树上点对的问题让我们想到了点分治。
考虑点分治的过程，我们要计算过当前根点的所有点对的gcd及其数量。根节点的约数个数是O(d)的，那么我们所有数与根节点的 $gcd$ 最多也只能是 $O(d)$ 种。
先枚举根节点的所有约数，复杂度是 $O(d)$ 。
对于每个子树我们可以用 $O(n)$ 的时间完成dfs、去重。然后我们有 $O(d^2)$ 的时间完成对所有前面的和现在这个子树的 $gcd$ 的一一枚举，然后在将这个子树添加到前面去。
然后这个点分治的过程应该是 $O(d n \log n)$ 的?复杂度比较迷。
不过能过，跑的很快。
代码
| |
| |
