套路题。
设 \(M=10^5\)。
设 \(f(i)\) 表示路径的 \(\gcd\) 恰好为 \(i\) 时候的贡献，则答案为 \(\sum_{i=1}^M i\times f(i)\)。
套路的，将限制变成路径的 \(\gcd\) 为 \(i\) 的倍数，设 \(g(i)\) 表示此时的贡献。
则有 \(f(i)=g(i)-\sum_{i\mid j,j\le M}f(j)\)。
\(g\) 是很好求的。
先将 \(1\sim M\) 中每个数的因子集合预处理求出来，然后对于一个点 \(i\)，将它加入新图 \(G_j\) 中，满足 \(j\mid a_i\)。
然后对于每张新图，对于每个连通块，都可以用换根轻松计算出贡献。
时间复杂度 \(\mathcal O(nD+n\ln n)\)，其中 \(D\) 表示 \(1\sim M\) 中因子最大的数的因子数量，为 \(128\)。
但是常数很小，无压力跑过。
Code：
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
typedef long long ll;
typedef vector <int> vi;
const int N = 100000, mod = 998244353;
int n;
int a[N+5];
vi E[N+5], g[N+5], p[N+5];
vi tmp;
bool vis[N+5], mark[N+5];
int f[N+5];
int sz[N+5];
void dfs(int u, int fa) {
sz[u] = vis[u] = 1, tmp.pb(u);
for (int v : E[u]) if (v != fa && mark[v]) dfs(v, u), sz[u] += sz[v];
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= N; ++i)
for (int j = i; j <= N; j += i)
p[j].pb(i);
for (int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
for (int j : p[a[i]]) g[j].push_back(i);
}
for (int i = 1, u, v; i < n; ++i) scanf("%d%d", &u, &v), E[u].pb(v), E[v].pb(u);
for (int i = 1; i <= N; ++i) {
for (int x : g[i]) mark[x] = 1, vis[x] = 0;
for (int x : g[i])
if (!vis[x]) {
tmp.clear();
dfs(x, 0);
for (int v : tmp) f[i] = (f[i] + 1ll * sz[v] * (sz[x] - sz[v]) % mod) % mod;
f[i] = (f[i] + 1ll * sz[x] * (sz[x] - 1) / 2 % mod) % mod;
}
for (int x : g[i]) mark[x] = 0;
}
for (int i = N; i; --i)
for (int j = i + i; j <= N; j += i)
f[i] = (f[i] - f[j] + mod) % mod;
int ans = 0;
for (int i = 1; i <= N; ++i) ans = (ans + 1ll * i * f[i] % mod) % mod;
printf("%d", ans);
return 0;
}