import sys # sys.setrecursionlimit(200005) # sys.set_int_max_str_digits(200005) int1 = lambda x: int(x)-1 pDB = lambda *x: print(*x, end="\n", file=sys.stderr) p2D = lambda x: print(*x, sep="\n", end="\n\n", file=sys.stderr) def II(): return int(sys.stdin.readline()) def LI(): return list(map(int, sys.stdin.readline().split())) def LLI(rows_number): return [LI() for _ in range(rows_number)] def LI1(): return list(map(int1, sys.stdin.readline().split())) def LLI1(rows_number): return [LI1() for _ in range(rows_number)] def SI(): return sys.stdin.readline().rstrip() dij = [(0, 1), (-1, 0), (0, -1), (1, 0)] # dij = [(0, 1), (-1, 0), (0, -1), (1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)] # inf = -1-(-1 << 31) inf = -1-(-1 << 62) # md = 10**9+7 md = 998244353 from collections import defaultdict class Sieve: def __init__(self, n): self.plist = [2] min_prime_factor = [2, 0]*(n//2+1) for x in range(3, n+1, 2): if min_prime_factor[x] == 0: min_prime_factor[x] = x self.plist.append(x) if x**2 > n: continue for y in range(x**2, n+1, 2*x): if min_prime_factor[y] == 0: min_prime_factor[y] = x self.min_prime_factor = min_prime_factor def isprime(self, x): return self.min_prime_factor[x] == x def pf(self, x): pp, ee = [], [] while x > 1: mpf = self.min_prime_factor[x] if pp and mpf == pp[-1]: ee[-1] += 1 else: pp.append(mpf) ee.append(1) x //= mpf return pp, ee # unsorted def factor(self, a): ff = [1] pp, ee = self.pf(a) for p, e in zip(pp, ee): ff, gg = [], ff w = p for _ in range(e): for f in gg: ff.append(f*w) w *= p ff += gg return ff sv=Sieve(10**6) class LCA: def __init__(self, parent, depth): n = len(parent) self._depth = depth log = max(self._depth).bit_length() self._table = [parent]+[[-1]*n for _ in range(log)] t0 = self._table[0] for lv in range(log): t1 = self._table[lv+1] for u in range(n): if t0[u] == -1: continue t1[u] = t0[t0[u]] t0 = t1 def anc(self, u, v): diff = self._depth[u]-self._depth[v] if diff < 0: u, v = v, u diff = abs(diff) u = self.up(u, diff) if u == v: return u for lv in range(self._depth[u].bit_length()-1, -1, -1): tl = self._table[lv] if tl[u] != tl[v]: u, v = tl[u], tl[v] return self._table[0][u] def up(self, u, dist): lv = 0 while dist and u != -1: if dist & 1: u = self._table[lv][u] lv, dist = lv+1, dist >> 1 return u n=II() aa=LI() to=[[] for _ in range(n)] for _ in range(n-1): u,v=LI1() to[u].append(v) to[v].append(u) def dfs(root=0): uu = [] stack = [root] while stack: u = stack.pop() if dfsOrder[u] == -1: dfsOrder[u] = len(uu) utoi[u] = len(eulerTour) eulerTour.append(u) uu.append(u) if u != root: stack.append(u) # !!! to's format for v in to[u]: if v == parent[u]: continue depth[v] = depth[u]+1 parent[v] = u stack.append(v) else: right[u] = len(uu) eulerTour.append(parent[u]) right[root] = len(uu) return uu eulerTour, utoi = [], [0]*n right = [-1]*n # left = dfsOrder parent, depth, dfsOrder = [-1]*n, [0]*n, [-1]*n uu=dfs() lca=LCA(parent,depth) p2u=defaultdict(list) pu2e={} for u in uu: pp,ee=sv.pf(aa[u]) for p,e in zip(pp,ee): p2u[p].append(u) pu2e[p,u]=e ans=[1]*n def auxiliary_tree(vv0,p): if len(vv0)==1: v=vv0[0] ans[v]=ans[v]*pow(p,pu2e[p,v],md)%md return st = set(vv0) for i in range(len(vv0)-1): st.add(lca.anc(vv0[i], vv0[i+1])) vv = sorted(st, key=lambda x: dfsOrder[x]) stack = [vv[0]] par = {} for u in vv[1:]: while right[stack[-1]] <= dfsOrder[u]: stack.pop() par[u] = stack[-1] stack.append(u) mx=defaultdict(int) sm=defaultdict(int) for v in vv[::-1]: if (p,v) in pu2e:mx[v]=max(mx[v],pu2e[p,v]) sm[v]+=mx[v] ans[v]=ans[v]*pow(p,sm[v],md)%md if v in par: u=par[v] mx[u]=max(mx[u],mx[v]) sm[u]-=mx[v] for p in p2u: auxiliary_tree(p2u[p],p) for u in uu[:0:-1]: v=parent[u] ans[v]=ans[u]*ans[v]%md print(*ans,sep="\n")