結果

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

ソースコード

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]=1
    d=f[ry][y]//f[rx][y]
    if d>0:
      f[rx][y]*=d
      a[rx]*=d
      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]=y**c
  if x>0:
    f[i][x]=x

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