[1033] 칵테일 (최소공배수, 최대공약수, 유클리드호제법)

1033번: 칵테일

 

분석

• 사이클이 없는 트리 구조이므로 임의의 노드에서 DFS를 진행하면서 해결
• DFS 과정에서 유클리드 호제법을 사용해 비율들의 최소공배수와 최대공약수를 구하고, 재료의 최소 질량을 구하는데 사용

 

풀이

"""
칵테일에 들어가는 재료 N개는 공개되어 있다.
총 재료 쌍 N-1개의 비율이 입력으로 주어진다.
칵테일을 만드는데 필요한 각 재료의 양
이때, 필요한 재료의 질량을 모두 더한 값이 최소가 되어야 한다.
a b p q : a번 재료의 질량을 b번 재료의 질량으로 나눈 값이 p/q라는 뜻이다.
"""
import math
import sys
input=sys.stdin.readline

n=int(input())  # 재료개수
A=[[] for _ in range(n)]  # 비율 리스트
visitList = [False]*n  # 방문체크
amount=[0]*n  # 각 재료의 양
lcm=1  # 최소공배수

# 깊이우선 탐색
def dfs(v):
    visitList[v] = True
    for i in A[v]:
        next=i[0]
        if not visitList[next]:
            amount[next]=amount[v]*i[2]//i[1]  #  * p/q
            dfs(next)

for _ in range(n-1):
    a,b,p,q=map(int, input().split())
    A[a].append((b,p,q))
    A[b].append((a,q,p))
    lcm*=(p*q)//math.gcd(p,q)

amount[0]=lcm
dfs(0)

# 최대 공약수 계산
mgcd=amount[0]
for i in range(1,n):
    mgcd=math.gcd(mgcd, amount[i])

for i in range(n):
    print(int(amount[i]/mgcd), end=' ')