Day 175-Q1 — 2026-10-11 | 赤青 Hackenbush の木を N=2×10^5 で（値を符号展開のまま持ち、和は短い側の桁数だけ書き換える）

📋 コピーimport sys

TO_SIGN = bytes.maketrans(b'10', b'+-')


def canon(z, k):
    # z / 2^k（k>0 なら z は奇数）の符号展開を (先頭の並びの符号, 並びの長さ, 小数部の符号列) で返す
    # 小数部は '1'=+ / '0'=- の bytes で、位 1/2 が先頭
    if k == 0:
        return (1 if z >= 0 else -1), abs(z), b''
    neg = z < 0
    if neg:
        z = -z
    m = z >> k
    f = z - (m << k)                       # 1..2^k-1 の奇数
    digits = format((f - 1) >> 1, '0%db' % k).encode()
    if neg:
        return -1, m + 1, digits.translate(bytes.maketrans(b'01', b'10'))
    return 1, m + 1, digits


def exact(o):
    # 符号展開 o を (分子, 指数) に。小数部の長さ k が指数
    sg, r, d = o
    k = len(d)
    if k == 0:
        return sg * r, 0
    pm = int(bytes(d[::-1]), 2)
    return (sg * r << k) + 2 * pm - (1 << k) + 1, k


def add(x, y):
    # x に y を足す（x を書き換える）。x の小数部が長いときは先頭 e+1 桁だけ作り直す
    ya, k = exact(y)
    sg, r, d = x
    if len(d) <= k + 1:
        xa, kx = exact(x)
        K = max(kx, k)
        z = (xa << (K - kx)) + (ya << (K - k))
        if z == 0:
            x[0], x[1], x[2] = 1, 0, bytearray()
            return
        t = min((z & -z).bit_length() - 1, K)
        nsg, nr, nd = canon(z >> t, K - t)
        x[0], x[1], x[2] = nsg, nr, bytearray(nd[::-1])
        return
    e = k
    if e:
        pm = int(bytes(d[-1:-e - 1:-1]), 2)
        xe = (sg * r << e) + 2 * pm - (1 << e) + 1
    else:
        xe = sg * r
    s = 1 if d[-e - 1] == 49 else -1       # 49 は b'1'（位 2^-(e+1) の符号）
    z = 2 * xe + 2 * ya + s                # 奇数。z / 2^(e+1) が新しい前半の値
    del d[-e - 1:]
    nsg, nr, nd = canon(z, e + 1)
    d.extend(nd[::-1])
    x[0], x[1] = nsg, nr


def push_edge(o, c):
    # 辺を 1 本下に足す = 符号展開の先頭に c（+1 青 / -1 赤）を付ける
    sg, r, d = o
    if r == 0 or sg == c:
        o[0] = c
        o[1] = r + 1
    else:
        d.extend((b'1' if sg > 0 else b'0') * r)
        o[0] = c
        o[1] = 1


def main():
    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]
    for v in order:
        order.extend(children[v])
    val = [None] * (n + 1)
    for v in reversed(order):
        ch = children[v]
        if not ch:
            o = [1, 0, bytearray()]
        else:
            best = max(ch, key=lambda c: len(val[c][2]))
            o = val[best]
            for c in ch:
                if c != best:
                    add(o, val[c])
                    val[c] = None
            val[best] = None
        if v != 1:
            push_edge(o, 1 if col[v - 2] == 66 else -1)
        val[v] = o
    sg, r, d = val[1]
    if r == 0:
        print(0)
        print("Red Blue")
        return
    s = (b'+' if sg > 0 else b'-') * r + bytes(d[::-1]).translate(TO_SIGN)
    sys.stdout.write(s.decode() + '\n')
    print("Blue Blue" if sg > 0 else "Red Red")


main()