#include #include using namespace std; using namespace atcoder; //using mint = modint1000000007; //const int mod = 1000000007; using mint = modint998244353; const int mod = 998244353; //const int INF = 1e9; //const long long LINF = 1e18; #define rep(i, n) for (int i = 0; i < (n); ++i) #define rep2(i,l,r)for(int i=(l);i<(r);++i) #define rrep(i, n) for (int i = (n) - 1; i >= 0; --i) #define rrep2(i,l,r)for(int i=(r) - 1;i>=(l);--i) #define all(x) (x).begin(),(x).end() #define allR(x) (x).rbegin(),(x).rend() #define P pair template inline bool chmax(A & a, const B & b) { if (a < b) { a = b; return true; } return false; } template inline bool chmin(A & a, const B & b) { if (a > b) { a = b; return true; } return false; } #include #include class Tree { public: Tree(int n, int root) : n(n), root(root) { edge.resize(n); for (int i = 0; i < MAXLOGV; i++) parent[i].resize(n); depth.resize(n); } // uとvをつなぐ // lcaを求めることが主目的なので無向グラフとしている void unite(int u, int v) { edge[u].push_back(v); edge[v].push_back(u); } // initする // コンストラクタだけじゃなくてこれも呼ばないとlcaが求められないぞ void init() { dfsOrder.resize(n); dfs(root, -1, 0); for (int k = 0; k + 1 < MAXLOGV; k++) { for (int v = 0; v < n; v++) { if (parent[k][v] < 0) parent[k + 1][v] = -1; else parent[k + 1][v] = parent[k][parent[k][v]]; } } } // uとvのlcaを求める int lca(int u, int v) const { if (depth[u] > depth[v]) std::swap(u, v); for (int k = 0; k < MAXLOGV; k++) { if ((depth[v] - depth[u]) >> k & 1) { v = parent[k][v]; } } if (u == v) return u; for (int k = MAXLOGV - 1; k >= 0; k--) { if (parent[k][u] != parent[k][v]) { u = parent[k][u]; v = parent[k][v]; } } return parent[0][u]; } // uのn個親を求める int pare(int v, int n) { if (depth[v] < n)return -1; n = std::min(n, depth[v]); int idx = MAXLOGV; while (n) { for (int i = idx - 1; i >= 0; --i) { if (n < (1 << i))continue; if (-1 == parent[i][v])continue; n -= (1 << i); v = parent[i][v]; idx = i; break; } } return v; } // uからvに向かってd進んだ頂点を返す int JumpOnTree(int u, int v, int d) { if (0 == d)return u; int distuv = dist(u, v); if (distuv < d)return -1; int l = lca(u, v); if (l == u)return pare(v, distuv - d); if (l == v)return pare(u, d); int distlu = dist(l, u); if (distlu >= d)return pare(u, d); return pare(v, distuv - d); } // uとvの距離を求める // edgeを定義しないといけない時はこれじゃダメ int dist(int u, int v) const { int p = lca(u, v); return (depth[u] - depth[p]) + (depth[v] - depth[p]); } //頂点wが頂点u,vのパス上に存在するか bool on_path(int u, int v, int w) { return (dist(u, w) + dist(v, w) == dist(u, v)); } int tmp = 0; int dfs(int v, int p, int d) { dfsOrder[v] = tmp; tmp++; int ret = 1; parent[0][v] = p; depth[v] = d; for (int next : edge[v]) { if (next == p) continue; auto get = dfs(next, v, d + 1); ret += get; } return ret; } static const int MAXLOGV = 25; // グラフの隣接リスト表現 std::vector>edge; // 頂点の数 int n; // 根ノードの番号 int root; // 親ノード std::vector parent[MAXLOGV]; // 根からの深さ std::vector depth; // dfsorder std::vectordfsOrder; }; class Osa_k { public: Osa_k(int max = 1000006) { osa_k.resize(max + 1); } void init() { osa_k[1] = 1; for (int i = 2; i < osa_k.size(); ++i) { if (0 != osa_k[i])continue; osa_k[i] = i; for (int j = i * 2; j < osa_k.size(); j += i) { if (0 == osa_k[j]) osa_k[j] = i; } } } std::vector osk(int n) { std::vectorresult; while (1 != n) { result.push_back(osa_k[n]); n /= osa_k[n]; } return result; } std::vector>oskPair(int n) { auto ps = osk(n); std::vector> result; for (int i = 0; i < ps.size();) { int j = i + 1; while (j < ps.size() && ps[i] == ps[j])j++; result.emplace_back(ps[i], j - i); i = j; } return result; } private: std::vectorosa_k; }; int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n; cin >> n; vectora(n); rep(i, n)cin >> a[i]; vector to(n, vector()); Tree tr(n, 0); rep(i, n - 1) { int u, v; cin >> u >> v; u--, v--; to[u].push_back(v); to[v].push_back(u); tr.unite(u, v); } tr.init(); vectororder(n); iota(all(order), 0); std::sort(order.begin(), order.end(), [&](int l, int r) { return tr.dfsOrder[l] < tr.dfsOrder[r]; } ); Osa_k osak; osak.init(); vector ps(1e6, vector()); for (auto e : order) { for (auto[p, q] : osak.oskPair(a[e])) { ps[p].push_back(e); } } vectorans(n); rep(i, n)ans[i] = a[i]; rep(p, ps.size()) { if (ps[p].empty())continue; mint ip = mint(p).inv(); auto ids = move(ps[p]); while (!ids.empty()) { int sz = ids.size(); rep(i, sz - 1) { int j = i + 1; ans[tr.lca(ids[i], ids[j])] *= ip; } int nsz = 0; rep(i, sz) { int v = ids[i]; a[v] /= p; if (a[v] % p)continue; ids[nsz++] = v; } ids.resize(nsz); } } rrep(i, n) { int v = order[i]; for (auto u : to[v])if (tr.dfsOrder[u] < tr.dfsOrder[v]) { ans[u] *= ans[v]; } } for (auto e : ans)cout << e.val() << endl; return 0; }