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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#!/usr/bin/env python
def gcd(a, b):
    if not b:
        return a
    return gcd(b, a % b)


def lcm(a, b):
    return a // gcd(a, b) * b


def simplify(a, b):
    gcd_v = gcd(a, b)
    a //= gcd_v
    b //= gcd_v

    return a, b


class Sol:
    def __init__(self, n):
        self.n = n
        self.input: list[int] = [0] * (n + 2)
        self.v: list[list[int]] = list(map(lambda _: [], range(n+2)))
        self.rv: list[list[int]] = list(map(lambda _: [], range(n+2)))

        self.resultA = [0] * (n + 2)
        self.resultB = [0] * (n + 2)

        self.v[0].append(1)
        self.rv[1].append(0)

        self.resultA[0] = self.resultA[n + 1] = 1
        self.resultB[0] = self.resultB[n + 1] = 1

        for i in range(1, n+1):
            r, *vals = input().split()
            for v in vals:
                self.v[i].append(int(v))

            if not int(r):
                self.v[i].append(n + 1)
                self.rv[n+1].append(i)

            self.resultA[i] = 1
            self.resultB[i] = 1

        self.dfs(1)

        q = [1]
        while q:
            val = q.pop()
            if val == n + 1:
                continue

            for child in self.v[val]:
                self.input[child] -= 1
                if not self.input[child]:
                    q.append(child)

            sum_a = 0
            sum_b = 1

            for parent in self.rv[val]:
                lcm_v = lcm(self.resultB[parent], sum_b)
                sum_a = lcm_v // sum_b * sum_a + lcm_v // self.resultB[parent] * self.resultA[parent]
                sum_b = lcm_v
                sum_a, sum_b = simplify(sum_a, sum_b)

                # print(f'Ja, {parent} daje tobie dziecku {val}')

            self.resultA[val] = sum_a
            self.resultB[val] = sum_b * len(self.v[val])
            self.resultA[val], self.resultB[val] = simplify(self.resultA[val], self.resultB[val])

            # print(f'Ja, {val}, daję każdemu dziecku {self.resultA[val]}/{self.resultB[val]}')

        final_time = 1
        for i in range(1, n+1):
            final_time = lcm(final_time, self.resultB[i])

        print(int(final_time))

    def dfs(self, val):
        for child in self.v[val]:
            self.input[child] += 1
            self.rv[child].append(val)
            if self.input[child] == 1:
                self.dfs(child)


if __name__ == '__main__':
    n = int(input())
    Sol(n)