#include #include #include using namespace std; using ll=long long; constexpr ll mod=998244353; vectorlpf; ll pow_mod(ll x,ll p){ if(p==1)return x; ll res=1; while(p){ if(p&1)res=(res*x)%mod; x=(x*x)%mod; p>>=1; } return res; } void init(int n){ lpf.resize(n+1,-1); for(int i=2;i<=n;i++)if(lpf[i]==-1){ for(int j=1;i*j<=n;j++)if(lpf[i*j]==-1){ lpf[i*j]=i; } } } vector>factorize(int n){ vector>res; while(n>1){ int p=lpf[n]; int e=0; while(n%p==0){ n/=p; e++; } res.emplace_back(p,e); } return res; } int main(){ int n; cin>>n; vectora(n); for(int i=0;i>a[i]; init(*max_element(a.begin(),a.end())); vector>g(n); for(int i=0;i>u>>v; u--,v--; g[u].push_back(v); g[v].push_back(u); } g[0].push_back(-1); auto hld=[&](auto self,int x,int p)->int { int res=1; int mx=-1; for(int&c:g[x]){ if(c==p){ if(g[x].back()==c)break; swap(g[x].back(),c); } int sz=self(self,c,x); if(mx>>a_fac(n); for(int i=0;ians(n); ll now=1; vectorpe(lpf.size()); auto set=[&](auto self,int x)->void { for(auto [p,e]:a_fac[x]){ if(pe[p]>=e)continue; now=(now*pow_mod(p,e-pe[p]))%mod; pe[p]=e; } for(int c:g[x])self(self,c); }; auto reset=[&](auto self,int x)->void { for(auto [p,e]:a_fac[x])pe[p]=0; for(int c:g[x])self(self,c); }; auto dfs=[&](auto self,int x)->void { for(int i=1;i=e)continue; now=(now*pow_mod(p,e-pe[p]))%mod; pe[p]=e; } ans[x]=now; }; dfs(dfs,0); for(int i=0;i