ABC248G

有趣的反演（？）题目，欧拉函数基础变化。

题意：给定一棵带点权树，定义一条路径的权值为覆盖点的数目乘以所有数的 $\gcd$，求所有路径（不含单点路径）的和。$n\leq 10 ^ 5, 1\leq a_i\leq n$。

做法 1（赛时做法）

考虑枚举 $d$，使得所有数都是 $d$ 的倍数，对所有连通块进行遍历，可以得到所有路径覆盖点的个数和。$\gcd$ 为 $d$ 的答案即为 $d | \gcd$ 的答案减去所有 $\gcd = 2d, 3d, \dots$ 的答案，倒序扫即可。时间复杂度 $O(nD + n\ln n)$，$D$ 表示 $n$ 以内最大因数个数。统计连通块的个数可以树形 DP 一下即可。

void dfs(int x)
{
	if (a[x] % d) return;
	sz[x] = dis[x] = 1, vis[x] = true;
	for (int v : g[x])
		if (!(a[v] % d) && !vis[v]) {
			dfs(v);
			ans[d] = (ans[d] + (LL) dis[v] * sz[x] + (LL) dis[x] * sz[v]) % Mod;
			adj(dis[x] += dis[v] - Mod), adj(dis[x] += sz[v] - Mod), sz[x] += sz[v];
		}
}

int main()
{
	for (int i = 1; i <= n; ++ i)
		for (int j = 1, x = a[i]; j <= x / j; ++ j) {
			if (x % j) continue;
			bs[j].push_back(i);
			if (j * j != x) bs[x / j].push_back(i);
		}
	for (d = 1; d < N; ++ d)
	{
		for (int x : bs[d])
			if (!vis[x]) dfs(x);
		for (int x : bs[d]) vis[x] = false;
	}
	for (int i = N - 1; i; -- i)
		for (int j = 2; j * i < N; ++ j) adj(ans[i] -= ans[i * j]);
    int res = 0;
	for (int i = 1; i < N; ++ i) res = (res + (LL) i * ans[i]) % Mod;
	std::cout << res << std::endl;
	return 0;
}

做法 2（欧拉函数）

考虑一件事情：$\sum_{d | n} \varphi(d) = n$，具体证明可以拆质数算。那么当贡献为 $n$ 时，我们只需要计算 $\sum_{d | n} \varphi(d)$ 即可。

向上面一样，我们直接计算 $d | \gcd$ 的路径点数之和，最后乘上 $\varphi(d)$ 即可。时间复杂度 $O(nD)$。

代码和上面差不多，不给了。