题意
给定一棵 $n$ 个点的无根树，每个点有点权，求长度为 $D$ 且满足路径点权的 $\gcd$ 大于 $1$ 的路径个数。
其中 $3 \le n \le 5 \cdot 10^5$，值域 $[1,30000]$。
分析
记 $f(n)$ 表示路径 $\gcd$ 和为 $n$ 的路径数，$g(n)$ 表示路径 $\gcd$ 为 $n$ 的倍数的路径数。
因此有
$$
g(d)=\sum_{d|n} f(d)
$$
由莫比乌斯反演
$$
f(d)=\sum_{d|n} \mu(\frac{n}{d}) g(n)
$$
因此答案 $S$ 就是
$$
S=\sum_{i=2}^\infty f(i)=\sum_{i=2}^\infty \sum_{i|d} \mu(\frac{d}{i}) g(d)
$$
交换求和顺序
$$
S=\sum_{d=1}^\infty g(d) \sum_{i>1 \land i|d} \mu(\frac{d}{i}) = \sum_{d=2}^\infty g(d)(0-\mu(d))
$$
于是只需要计算 $g(d)$ 即可，枚举值域 $i \in [2,30000]$ 且 $\mu(i) \neq 0$，计算有多少条长度为 $D$ 的路径的点权都是 $i$ 的倍数。将这些点拿出来，显然是这个点集构成一个森林，下面考虑一棵树的情况。记 $dp(u,i)$ 表示以 $u$ 为根节点的子树内距离 $u$ 为 $i$ 的点数。状态数和转移的复杂度都是 $O(n^2)$ 的，套用长链剖分优化关于深度信息合并的技巧，可以做到 $O(n)$ 的时空求出这个 $dp$ 数组。
