테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== 칵테일 ======

===== 풀이 =====
  * 사실 n이 워낙 작아서 어떤 방식으로 풀든 시간안에 풀리기는 한다
  * 칵테일의 재료를 노드로, 비율이 주어진 재료쌍을 엣지로 하는 그래프를 생각하자.
  * 문제가 약간 애매하게 쓰여있는데, "이 비율을 이용해서 칵테일에 들어가는 전체 재료의 비율을 알아낼 수 있다" 라는 말이 결국 모든 노드들이 연결되어 있다는 것을 의미한다. 이제 엣지의 갯수가 N-1개이므로, 그래프가 트리라는 것도 알 수 있다.
  * 트리라는 것을 알면 이후는 간단하다. 노드 한개를 루트로 놓고, 질량을 X라고 고정하면, 다른 노드들의 질량은 부모노드의 질량에 비율을 곱해서 모두 구할 수 있다.
  * 모든 노드의 질량을 X*p[u]/q[u] 형태로 표현하고 나면 (p[u]/q[u]는 기약분수), X의 최솟값은 모든 q[u]의 최소공배수가 된다. 이 값을 구해주면 끝. 
  * 트리를 탐색하며 각 노드의 비율을 계산하는데에 O(n), lcm을 구하는데에 O(n*logm)이 걸리므로 총 시간복잡도는 O(nlogm)이다
  * 분자와 분모를 따로 계산해서 저장하는 방법과, 그냥 fractions 라이브러리를 쓰는 방법 두가지로 구현했는데, fractions를 쓸 때가 코드는 간단했지만 시간은 훨씬 오래 걸렸다.

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 1033. 칵테일".

- Problem link: https://www.acmicpc.net/problem/1033
- Solution link: http://www.teferi.net/ps/problems/boj/1033

Tags: [math]
"""

import math
import fractions


def main():
    N = int(input())
    wtree = [{} for _ in range(N)]
    for _ in range(N - 1):
        a, b, p, q = [int(x) for x in input().split()]
        wtree[a][b] = fractions.Fraction(q, p)
        wtree[b][a] = fractions.Fraction(p, q)

    ratio = [fractions.Fraction(1) for _ in range(N)]
    root = 0
    stack = [root]
    visited = [False] * N
    visited[root] = True
    while stack:
        u = stack.pop()
        for v, w in wtree[u].items():
            if visited[v]:
                continue
            visited[v] = True
            ratio[v] = ratio[u] * w
            stack.append(v)
    lcm = math.lcm(*(ratio_u.denominator for ratio_u in ratio))
    answer = [ratio_u * lcm for ratio_u in ratio]

    print(*answer)


if __name__ == '__main__':
    main()
</dkpr>

{{tag>BOJ ps:problems:boj:골드_2}}