結果

問題 No.3250 最小公倍数
ユーザー LyricalMaestro
提出日時 2025-10-11 17:37:16
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,996 bytes
コンパイル時間 375 ms
コンパイル使用メモリ 82,556 KB
実行使用メモリ 338,640 KB
最終ジャッジ日時 2025-10-11 17:37:47
合計ジャッジ時間 29,884 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 3 WA * 14 TLE * 1 -- * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

## 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
    while len(stack) > 0:
        v, index = stack.pop()
        if index == 0:
            answer1[v] *= A1[v]
            answer1[v] %= MOD

        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:
                answer1[p] *= answer1[v]
                answer1[p] %= MOD
    
    # 一定以下のものについて
    stack = deque()
    stack.append((0, 0))
    answer2 = [{} for _ in range(N)]
    while len(stack) > 0:
        v, index = stack.pop()
        if index == 0:
            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:
                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()
0