## https://yukicoder.me/problems/no/3250 import math from collections import deque MOD = 998244353 def main(): N = int(input()) A = list(map(int, input().split())) next_nodes = [[] for _ in range(N)] for _ in range(N - 1): u, v = map(int, input().split()) next_nodes[u - 1].append(v - 1) next_nodes[v - 1].append(u - 1) sqrt_max_a = int(math.sqrt(max(A))) primes = [] is_prime = [True] * (sqrt_max_a + 1) for p in range(2, sqrt_max_a + 1): if not is_prime[p]: continue primes.append(p) x = 2 * p while x <= sqrt_max_a: is_prime[x] = False x += p A1 = [] # 一定以上 A2 = [] # 一定以下 for a in A: b = {} for p in primes: while a % p == 0: if p not in b: b[p] = 0 b[p] += 1 a //= p A1.append(a) A2.append(b) # 一定以上のものについて stack = deque() parents = [-2] * N parents[0] = -1 stack.append((0, 0)) answer1 = [1] * N answer2 = [{} for _ in range(N)] answer1_set = [set() for _ in range(N)] while len(stack) > 0: v, index = stack.pop() if index == 0: answer1[v] *= A1[v] answer1[v] %= MOD answer1_set[v].add(A1[v]) v_map = A2[v] for p, v_ind in v_map.items(): if p not in answer2[v]: answer2[v][p] = 0 answer2[v][p] = max(answer2[v][p], v_ind) while index < len(next_nodes[v]): w = next_nodes[v][index] if w == parents[v]: index += 1 continue parents[w] = v stack.append((v, index + 1)) stack.append((w, 0)) break if index == len(next_nodes[v]): p = parents[v] if p != -1: a_set1 = answer1_set[p] a_set2 = answer1_set[v] if len(a_set1) >= len(a_set2): value = answer1[p] for prime in a_set2: if prime not in a_set1: value *= prime value %= MOD a_set1.add(prime) answer1[p] = value answer1_set[p] = a_set1 else: value = answer1[v] for prime in a_set1: if prime not in a_set2: value *= prime value %= MOD a_set2.add(prime) answer1[p] = value answer1_set[p] = a_set2 v_map = answer2[v] for p_, v_ind in v_map.items(): if p_ not in answer2[p]: answer2[p][p_] = 0 answer2[p][p_] = max(answer2[p][p_], v_ind) for i in range(N): answer = answer1[i] for p, v_ind in answer2[i].items(): answer *= pow(p, v_ind, MOD) answer %= MOD print(answer) if __name__ == '__main__': main()