結果

問題 No.3250 最小公倍数
ユーザー sasa8uyauya
提出日時 2025-08-30 02:03:27
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,065 bytes
コンパイル時間 406 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 191,204 KB
最終ジャッジ日時 2025-08-30 02:03:33
合計ジャッジ時間 5,124 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 4 TLE * 1 -- * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

n=int(input())
a=list(map(int,input().split()))
e=[[] for i in range(n)]
for i in range(n-1):
  u,v=map(int,input().split())
  u-=1
  v-=1
  e[u]+=[v]
  e[v]+=[u]
M=998244353

def union(x,y):
  rx=root(x)
  ry=root(y)
  if rx==ry:
    return
  if len(f[rx])<len(f[ry]):
    rx,ry=ry,rx
  r[ry]=rx
  for y in f[ry]:
    if y not in f[rx]:
      f[rx][y]=0
    a[rx]*=pow(pow(y,f[rx][y],M),M-2,M)
    f[rx][y]=max(f[rx][y],f[ry][y])
    a[rx]*=pow(y,f[rx][y],M)
    a[rx]%=M
  return

def root(x):
  p=x
  l=[p]
  while r[p]!=p:
    p=r[p]
    l+=[p]
  for p in l:
    r[p]=l[-1]
  return r[x]

r=list(range(n))

f=[{} for i in range(n)]
for i in range(n):
  x=a[i]
  for y in range(2,a[i]+1):
    if y*y>x:
      break
    c=0
    while x%y==0:
      x//=y
      c+=1
    if c>0:
      f[i][y]=c
  if x>0:
    f[i][x]=1

v=[0]*n
u=[0]*n
q=[0]
while len(q)>0:
  s=q[-1]
  if v[s]==0:
    v[s]=1
    q+=[t for t in e[s] if v[t]==0]
  else:
    for t in e[s]:
      if v[t]==0:
        union(s,t)
    rs=root(s)
    u[s]=a[rs]
    v[s]=0
    q.pop()

print(*u,sep="\n")
0