Day 172-Q1 — 2026-10-08 | 根付き木の赤青 Hackenbush（部分木の値を「一番簡単な数」の規則で下から合成し、既約分数で出力する）

📋 コピーimport sys


def main():
    sys.set_int_max_str_digits(0)           # 分母 2^e の 10 進表記は 4300 桁を超えうる
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    par = [0, 0] + [int(x) for x in data[1:n]]
    col = data[n] if n > 1 else b''
    children = [[] for _ in range(n + 1)]
    for v in range(2, n + 1):
        children[par[v]].append(v)
    order = [1]                             # BFS 順。逆順にたどると子が親より先に終わる
    for v in order:
        order.extend(children[v])
    num = [0] * (n + 1)                     # 頂点 v の上に載っている値 = num[v] / 2^ex[v]（既約）
    ex = [0] * (n + 1)
    for v in reversed(order):
        if v == 1:
            break
        a, e = num[v], ex[v]
        blue = col[v - 2] == 66             # 66 は b'B'
        if not blue:
            a = -a                          # 赤い辺は「色を反転した青い辺」として計算する
        if a >= 0:
            a += 1 << e                     # x >= 0 なら青い辺を足すと x + 1
        else:
            if a.bit_length() <= e:         # -1 < x < 0 なら k = 2（大きな整数を作らない近道）
                k = 2
            else:
                k = ((1 << e) - a >> e) + 1  # x + k > 1 となる最小の正整数 k
            a += k << e                     # (x + k) / 2^(k-1)
            e += k - 1
            if not a & 1:                   # 偶数のときだけ約分（奇数なら既約）
                t = min((a & -a).bit_length() - 1, e)
                a >>= t
                e -= t
        if not blue:
            a = -a
        p = par[v]                          # 親の上の値に足し込む（指数を大きい方にそろえる）
        pa, pe = num[p], ex[p]
        if pa == 0:
            num[p], ex[p] = a, e
            continue
        if pe >= e:
            pa += a << (pe - e)
        else:
            pa = (pa << (e - pe)) + a
            pe = e
        if pa == 0:
            pe = 0
        elif not pa & 1 and pe:
            t = min((pa & -pa).bit_length() - 1, pe)
            pa >>= t
            pe -= t
        num[p], ex[p] = pa, pe
    a, e = num[1], ex[1]
    print(str(a) if e == 0 else f"{a}/{1 << e}")
    print("Blue Blue" if a > 0 else "Red Red" if a < 0 else "Red Blue")


main()