社贡已经掉没了，赶紧写发题解。

考虑枚举 $\gcd$，$f(d)$ 表示 $\gcd=d$ 时路径长度之和，答案就是 $\sum d\cdot f(d)$。

但这个玩意不好求，于是考虑求 $d \mid \gcd$ 时路径长度之和 $g(d)$，在根据 $g(d)$ 容斥递推出 $f(d)$：

$f(d)=g(d)-\sum_{k>1} f(kd)$

接下来的问题就是求 $g(d)$，$d \mid \gcd$ 等价于 $d \mid a_1,a_2,...,a_m$，我们枚举 $d$，把所有 $d \mid a_i$ 的 $i$ 拿出来，构成了好几颗树（森林）。

现在问题又变成了求这些树的路径长度之和，我们枚举一条边 $(u,v)$，算它被经过了多少次。这个也很好算，一定是从 $v$ 的子树内走向子树外，及 $sz_v(m-sz_v)$，其中 $m$ 是树的大小。哦对了，题目的路径长度是点的数量，所以要加上 $\frac{m(m-1)}{2}$。

然后就做完了，时间复杂度为 $O(n\max{d(a_i)}+V\ln{V})$。$d(a_i)$ 是约数个数，$10^5$ 以内最大只有 $128$，8s 时限轻松 AC。

#include<bits/stdc++.h>
#define pb emplace_back
using namespace std;
typedef long long ll;
const ll N=1e5+5,P=998244353;
ll n,u,v,ans,a[N],g[N],sz[N],vis[N],b[N],lb;
vector<ll> G[N],fac[N],c[N];
void dfs(ll x,ll s){
	sz[x]=vis[x]=1;
	for(ll y:G[x]){
		if(a[y]%s||vis[y]) continue;
		dfs(y,s);b[++lb]=sz[y];
		sz[x]+=sz[y];
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin>>n;
	for(ll i=1;i<=1e5;i++){
		for(ll j=i;j<=1e5;j+=i) fac[j].pb(i);
	}
	for(ll i=1;i<=n;i++){
		cin>>a[i];
		for(ll x:fac[a[i]]) c[x].pb(i);
	}
	for(ll i=1;i<n;i++){
		cin>>u>>v;
		G[u].pb(v);G[v].pb(u);
	}
	for(ll i=1;i<=1e5;i++){
		for(ll j:c[i]) vis[j]=0;
		for(ll j:c[i]){
			if(!vis[j]){
				lb=0;dfs(j,i);
				for(ll k=1;k<=lb;k++) (g[i]+=(sz[j]-b[k])*b[k])%=P;
				(g[i]+=sz[j]*(sz[j]-1)/2)%=P; 
			}
		}
	}
	for(ll i=1e5;i;i--){
		for(ll j=i+i;j<=1e5;j+=i) (g[i]-=g[j])%=P;
		(ans+=(g[i]+P)*i)%=P;
	}
	cout<<ans;
	return 0;
}