$rt$

复杂度O($NlogN+k$）（k是所有a[i]因数个数之和，5e5以内因数个数最多的数约有200个因数，上限应该是5e7，实际不可能卡满）

黔驴技穷了，我能想到的优化都试了，还是死在最后四个测试点上。

附上代码，望各位dalao提点一下。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=2e5+3,M=5e5+3,MOD=998244353,ni2=MOD/2+1;
int n,a[N],h[N],idx;
int mx,mul[M],out[M],p[M],pnum;
int fa[N],d[N],dfn[N],now;
int seq[N<<1],deep[N<<1],first[N],st[20][N<<1],num;
LL sum[N],F[N],ans[N];
int stk[N],tp,val[N];
vector<int>v[M];
int read(){
	int x=0;
	char c=getchar();
	while(c>'9'||c<'0') c=getchar();
	while(c<='9'&&c>='0'){
		x=x*10+c-'0';
		c=getchar();
	}
	return x;
}
void print(LL x){
	if(x>=10) print(x/10);
	putchar(x%10+'0');
}
struct node{
	int v,ne;
}e[N<<1];
void add(int x,int y){
	e[++idx]={y,h[x]};
	h[x]=idx;
	//cout<<":"<<x<<' '<<y<<":"<<endl;
}
void work(int x){
	for(int i=1;i*i<=a[x];i++)
	    if(a[x]%i==0){
	    	v[i].emplace_back(x);
	    	if(i*i<a[x]) v[a[x]/i].emplace_back(x);
		}	
}
void get_mul(){
	mul[1]=1;
	for(int i=2;i<=mx;i++){
		if(!out[i]) mul[i]=-1,p[++pnum]=i;
		for(int j=1;j<=pnum&&i*p[j]<=mx;j++){
			out[i*p[j]]=1;
			if(i%p[j]==0) break;
			mul[i*p[j]]=-mul[i];
		}
	}
}
void get_LCA(){
	for(int i=1;i<=num;i++) st[0][i]=i;
	for(int i=1;i<=__lg(num);i++)
	    for(int j=1;j+(1<<i)-1<=num;j++){
	    	int l=st[i-1][j],r=st[i-1][j+(1<<i-1)];
	    	if(deep[l]<deep[r]) st[i][j]=l;
	    	else st[i][j]=r;
		}
}
int LCA(int x,int y){
	int l=first[x],r=first[y];
	if(l>r) swap(l,r);
	int len=__lg(r-l+1);
	int L=st[len][l],R=st[len][r-(1<<len)+1];
	return deep[L]<deep[R]?seq[L]:seq[R];
}
void dfs1(int u){
	dfn[u]=++now;work(u);
	for(int i=h[u];i;i=e[i].ne){
		int v=e[i].v;
		if(v==fa[u]) continue;
		fa[v]=u;d[v]=d[u]+1;
		dfs1(v);
	}
}
void dfs2(int u){
	seq[++num]=u,deep[num]=d[u],first[u]=num;
	for(int i=h[u];i;i=e[i].ne){
		int v=e[i].v;
		if(v==fa[u]) continue;
		dfs2(v);
		seq[++num]=u,deep[num]=d[u];
	}
}
void dfs3(int u,int k){
	F[u]=0;
	sum[u]=val[u];
	for(int i=h[u];i;i=e[i].ne){
		int v=e[i].v;
		dfs3(v,k);
		sum[u]+=sum[v];
		F[u]-=sum[v]*sum[v]*k;
	}
	sum[u]%=MOD;
	F[u]=(F[u]+sum[u]*sum[u]*k-1ll*val[u]*val[u]*k)%MOD;
	F[u]=F[u]*ni2%MOD;
	ans[u]+=F[u];
	h[u]=0;val[u]=0;
	//cout<<u<<' '<<sum[u]<<' '<<ans[u]<<' '<<F[u]<<endl;
}
void insert(int u){
	if(!tp){
		stk[++tp]=u;
		return;
	}
	int lca=LCA(u,stk[tp]);
	while(tp>1&&d[lca]<d[stk[tp-1]]) add(stk[tp-1],stk[tp]),tp--;
	if(d[lca]<d[stk[tp]]) add(lca,stk[tp]),tp--;
	if(lca!=stk[tp]) stk[++tp]=lca;
	stk[++tp]=u;
}
int Main()
{
    n=read();
	for(int i=1;i<=n;i++){
    	a[i]=read();
		mx=max(mx,a[i]);
    }
	get_mul();
	for(int i=1;i<n;i++){
		int x,y;
		x=read(),y=read();
		add(x,y),add(y,x);
	}
	dfs1(1);
	dfs2(1);
	get_LCA();
	memset(h,0,sizeof h);
	for(int i=2;i<=mx;i++){
		if(v[i].size()<2||!mul[i]) continue;
		//cout<<i<<":";
	    tp=idx=0;
		//for(int j=0;j<v[i].size();j++) cout<<v[i][j]<<' ';cout<<endl;
		for(int j=0;j<v[i].size();j++) val[v[i][j]]=a[v[i][j]];
		if(v[i][0]!=1) insert(1);
		for(int j=0;j<v[i].size();j++) insert(v[i][j]);
		while(tp>1) add(stk[tp-1],stk[tp]),tp--;
		dfs3(1,-mul[i]);
		//cout<<i<<":";for(int j=1;j<=n;j++) cout<<(ans[j]+MOD)%MOD<<' ';cout<<endl;
	}
	for(int i=1;i<=n;i++) print((ans[i]%MOD+MOD)%MOD),puts("");
	return 0;
}
int main()
{
    int Case=1;
    while(Case--) Main();
	return 0;
}