RT，数论和淀粉质好久没做来复健一下。

AC 23个点，TLE 16个点。

Code：

#include<iostream>
#include<vector>
#include<algorithm>
#pragma GCC optimize(2)
using namespace std;
typedef long long ll;
const ll mod=998244353;
vector<ll> G[100005],vc[100005];
ll n,u,v,w[100005],e[100005],ans,c[100005],f[100005],g[100005],d[100005],mxid,mx,sum,sz[100005],a[100005],b[100005],r,vis[100005];
void shai(int n){
	a[0]=a[1]=1;
	e[1]=1;
	for(int i=2;i<=n;i++){
		if(!a[i]){
			b[++r]=i;
			e[i]=i-1;
		}
		for(int j=1;j<=r&&i*b[j]<=n;j++){
			a[i*b[j]]=1;
			if(i%b[j]==0){
				e[i*b[j]]=e[i]*b[j]%mod;
				break;
			}
			e[i*b[j]]=e[i]*e[b[j]]%mod;
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=i;j<=n;j+=i){
			vc[j].push_back(i);
		} 
	}
}
void dfs(int x,int fat){
	if(vis[x]){
		return ;
	}
	sum++;
	sz[x]=1;
	for(int i=0;i<G[x].size();i++){
		if(G[x][i]!=fat&&(!vis[G[x][i]])){
			dfs(G[x][i],x);
			sz[x]+=sz[G[x][i]];
		}
	}
}
void dfs2(int x,int fat){
	if(vis[x]){
		return ;
	}
	int ret=sum-sz[x];
	for(int i=0;i<G[x].size();i++){
		if(G[x][i]!=fat&&(!vis[G[x][i]])){
			dfs2(G[x][i],x);
			ret=max(ret,(int)sz[G[x][i]]);
		}
	}
	if(ret<mx){
		mx=ret;
		mxid=x;
	}
}
void dfs3(int x,int fat,ll c,ll d){
	if(vis[x]){
		return ;
	}
//	cout<<x<<" "<<fat<<" "<<c<<" "<<d<<endl; 
	ans+=(c+1)*d%mod;
	ans%=mod;
	for(ll i=0;i<vc[d].size();i++){
	//	cout<<x<<" "<<fat<<" "<<c<<" "<<d<<" "<<vc[d][i]<<" "<<f[vc[d][i]]<<endl; 
		ans+=(c+1)*f[vc[d][i]]%mod;
		ans%=mod;
	}
	for(ll i=0;i<vc[d].size();i++){
		ans+=g[vc[d][i]];
		ans%=mod;
	}
	for(int i=0;i<G[x].size();i++){
		if(G[x][i]!=fat&&(!vis[G[x][i]])){
			dfs3(G[x][i],x,c+1,__gcd(d,w[G[x][i]]));
		}
	}
}
void dfs4(int x,int fat,ll c,ll d){
	if(vis[x]){
		return ;
	}
	for(ll i=0;i<vc[d].size();i++){
		f[vc[d][i]]+=e[vc[d][i]];
		f[vc[d][i]]%=mod;
		g[vc[d][i]]+=e[vc[d][i]]*c%mod;
		g[vc[d][i]]%=mod;
	}
	for(int i=0;i<G[x].size();i++){
		if(G[x][i]!=fat&&(!vis[G[x][i]])){
			dfs4(G[x][i],x,c+1,__gcd(d,w[G[x][i]]));
		}
	}
}
void dfs5(int x,int fat,ll c,ll d){
	if(vis[x]){
		return ;
	}
	for(ll i=0;i<vc[d].size();i++){
		f[vc[d][i]]=g[vc[d][i]]=0;
	}
	for(int i=0;i<G[x].size();i++){
		if(G[x][i]!=fat&&(!vis[G[x][i]])){
			dfs5(G[x][i],x,c+1,__gcd(d,w[G[x][i]]));
		}
	}
}
void DFS(int x){
	dfs(x,0);
	mx=mxid=0;
	mx=1e9;
	dfs2(x,0);
	x=mxid;
	vis[x]=1;
	c[x]=0;
//	cout<<"ZX "<<w[x]<<endl;
	for(int i=0;i<G[x].size();i++){
		if(!vis[G[x][i]]){
			dfs3(G[x][i],x,1,__gcd(w[x],w[G[x][i]]));
			dfs4(G[x][i],x,1,__gcd(w[x],w[G[x][i]]));
		}
	}
	for(int i=0;i<G[x].size();i++){
		if(!vis[G[x][i]]){
			dfs5(G[x][i],x,1,__gcd(w[x],w[G[x][i]]));
		}
	}
	for(int i=0;i<G[x].size();i++){
		if(!vis[G[x][i]]){
			DFS(G[x][i]);
		}
	}
}
int main(){
	cin>>n;
	for(ll i=1;i<=n;i++){
		cin>>w[i];
	}
	for(ll i=1;i<=n-1;i++){
		cin>>u>>v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	shai(100000);
	DFS(1);
	cout<<ans;
	return 0;
} 

@General0826 gengen队能不能出动？