#include #include using namespace std; using i32 = int; using i64 = long long; using f64 = double; using p2 = pair; using el = tuple; using mint = atcoder::modint998244353; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); } i32 n; i32 siz[500000]; i32 idx[500000], jdx[500000]; mint inv[1000001]; vector preo; vector g[500000]; vector P; vector> fac[500000]; void dfs1(i32 v, i32 par) { siz[v] = 1; idx[v] = jdx[v] = preo.size(); preo.push_back(v); for (i32 nv : g[v]) { if (nv != par) { dfs1(nv, v); siz[v] += siz[nv]; jdx[v] = jdx[nv]; } } } vector mxp; mint now; mint ans[500000]; void dfs2(i32 v, i32 par, bool keep) { i32 mxc = -1, vh = -1; for (i32 nv : g[v]) if (nv != par && mxc < siz[nv]) mxc = siz[nv], vh = nv; for (i32 nv : g[v]) if (nv != par && nv != vh) { dfs2(nv, v, false); } if (vh != -1) dfs2(vh, v, true); else now = 1; for (i32 nv : g[v]) if (nv != par && nv != vh) { for (i32 i = idx[nv]; i <= jdx[nv]; i++) { for (auto [id, s] : fac[preo[i]]) { if (mxp[id] < s) { now *= inv[mxp[id]]; now *= s; mxp[id] = s; } } } } for (auto [id, s] : fac[v]) { if (mxp[id] < s) { now *= inv[mxp[id]]; now *= s; mxp[id] = s; } } ans[v] = now; if (keep) return; for (i32 i = idx[v]; i <= jdx[v]; i++) { for (auto [id, s] : fac[preo[i]]) { mxp[id] = 1; } } now = 1; } void _main() { static i32 mod = 998244353; inv[1] = 1; for (i32 i = 2; i <= 1000000; i++) inv[i] = -inv[mod % i] * (mod / i); cin >> n; { vector>> prime(1000001); for (i32 i = 2; i <= 1000000; i++) { if (!prime[i].empty()) continue; i32 id = P.size(); P.push_back(i); prime[i].emplace_back(id, i); for (i32 j = i * 2; j <= 1000000; j += i) { i32 x = 1; while (j % (x * i) == 0) x *= i; prime[j].emplace_back(id, x); } } for (i32 i = 0; i < n; i++) { i32 x; cin >> x; fac[i] = prime[x]; } } for (i32 i = 0; i < n - 1; i++) { i32 u, v; cin >> u >> v; u--, v--; g[u].push_back(v); g[v].push_back(u); } mxp = vector(P.size(), 1); dfs1(0, -1); dfs2(0, -1, false); for (i32 i = 0; i < n; i++) cout << ans[i].val() << "\n"; }