-
Notifications
You must be signed in to change notification settings - Fork 0
/
1033.py
59 lines (42 loc) · 1.2 KB
/
1033.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
from sys import stdin
from collections import deque
input = stdin.readline
ans: list[int]
queue: deque[tuple[int, ...]] = deque()
# 유클리드 호제법을 이용한 최대공약수
def GCD(x, y):
while y:
x, y = y, x % y
return x
# 최대공약수를 이용한 최소공배수 구하기
def LCM(x, y):
return (x * y) // GCD(x, y)
def mul_list(n: int):
for i in range(len(ans)):
ans[i] *= n
def solve():
while queue:
a, b, p, q = queue.popleft()
if ans[a] or ans[b]:
common_idx, target_idx = (a, b) if ans[a] else (b, a)
common_val, target_val = (p, q) if ans[a] else (q, p)
lcm = LCM(ans[common_idx], common_val)
mul_list(lcm // ans[common_idx])
ans[target_idx] = target_val * (lcm // common_val)
else:
queue.append((a, b, p, q))
if __name__ == '__main__':
n = int(input())
ans = [0] * n
for i in range(n - 1):
a, b, p, q = map(int, input().split())
gcd = GCD(p, q)
p //= gcd
q //= gcd
if i == 0:
ans[a] = p
ans[b] = q
else:
queue.append((a, b, p, q))
solve()
print(*ans)