Day 149-Q4 | LOUDS（簡潔木表現）

問題

N個のノード（0始まり）からなる根付き木が与えられる。頂点0が根、頂点i（$1\le i\le N-1$）の親はpar_i（$par_i<i$）で与えられ、頂点番号はBFS順と一致することが保証される。この木を以下の手順でLOUDS bit stringに変換せよ。

エンコード手順

ただ1つの子（実際の根）を持つ仮想の「超根」を考える。
B = 超根の"1"×1+"0" に続けて、頂点0,1,...,N-1（BFS順）の各deg(v)個の"1"+"0"を連結。
B中のk番目（0-indexed）の0ビットが「LOUDSノードk」（k=0が超根、k=v+1が頂点v）。

親子の求め方（rank/selectのみ使用）

# ノードx(x>=1)の親: p = select1(x-1); parent = rank0(p)
# ノードxの子: start=0 if x==0 else select0(x-1)+1 ; end=select0(x)
#   position pのB[p]=='1'なら y=rank1(p+1)-1 ; 子は y+1

制約

$2 \le N \le 15$

頂点番号はBFS順（$par_i<i$）

$1 \le Q \le 10$

クエリはP x（親）またはC x（子）

入出力例

入力例1

7
0 0 1 1 2 5
5
P 3
C 1
P 0
C 5
C 3

出力例1

101101101000100
1
3 4
-1
6

木: 0→1,2 / 1→3,4 / 2→5 / 5→6。最終行は「頂点3に子が無い」ことを表す空行。

概念図：木構造とLOUDSビット列の対応

ヒント（段階的開示）

ヒント1（方向性）

BFS順で番号が振られていることが本質的。LOUDSでは「ある頂点の子」は必ずBFSでその頂点より後に処理される連続したブロックとしてBに現れる。ポインタの代わりに位置情報だけで親子関係を復元できる。

ヒント2（アプローチ）

B中のk番目の0ビットが「ノードk」の終端であり、k番目の1ビットは「ノードk+1」が誰の子として生成されたかを示す辺そのもの。この対応関係からrank/selectだけで親子を導出できる。

ヒント3（誘導）

def rank1(B, i): return B[:i].count('1')
def rank0(B, i): return B[:i].count('0')
def select1(B, k):
    c = -1
    for i, ch in enumerate(B):
        if ch == '1':
            c += 1
            if c == k: return i
def select0(B, k):
    c = -1
    for i, ch in enumerate(B):
        if ch == '0':
            c += 1
            if c == k: return i

模範解答 (Python)

import sys
from collections import deque


def build_louds(n, children):
    order = []
    q = deque([0])
    while q:
        u = q.popleft()
        order.append(u)
        for c in children[u]:
            q.append(c)
    B = ['1', '0']
    for u in order:
        B.append('1' * len(children[u]))
        B.append('0')
    return ''.join(B), order


def rank1(B, i):
    return B[:i].count('1')


def rank0(B, i):
    return B[:i].count('0')


def select1(B, k):
    c = -1
    for i, ch in enumerate(B):
        if ch == '1':
            c += 1
            if c == k:
                return i


def select0(B, k):
    c = -1
    for i, ch in enumerate(B):
        if ch == '0':
            c += 1
            if c == k:
                return i


def louds_parent(B, x):
    p = select1(B, x - 1)
    return rank0(B, p)


def louds_children(B, x):
    end = select0(B, x)
    start = 0 if x == 0 else select0(B, x - 1) + 1
    kids = []
    for p in range(start, end):
        if B[p] == '1':
            y = rank1(B, p + 1) - 1
            kids.append(y + 1)
    return kids


def main():
    data = sys.stdin.read().split('\n')
    idx = 0
    N = int(data[idx]); idx += 1
    children = [[] for _ in range(N)]
    if N > 1:
        pars = list(map(int, data[idx].split())); idx += 1
        for i, p in enumerate(pars, start=1):
            children[p].append(i)
    else:
        idx += 1
    Q = int(data[idx]); idx += 1

    B, order = build_louds(N, children)
    real_to_louds = {u: i + 1 for i, u in enumerate(order)}
    louds_to_real = {v: u for u, v in real_to_louds.items()}

    out = [B]
    for _ in range(Q):
        parts = data[idx].split(); idx += 1
        typ, x = parts[0], int(parts[1])
        lx = real_to_louds[x]
        if typ == 'P':
            if lx == 1:
                out.append("-1")
            else:
                lp = louds_parent(B, lx)
                out.append(str(louds_to_real[lp]))
        else:
            kids = louds_children(B, lx)
            kids_real = sorted(louds_to_real[k] for k in kids)
            out.append(' '.join(map(str, kids_real)))
    print('\n'.join(out))


main()

Step-by-Step 解説

1超根を導入する理由
実際の根にも「誰かの子である」体裁を与えないと、親の逆算式が根で破綻する。超根を先頭に置くことで全ノードが一様な式で扱える。

2「k番目の0ビット＝ノードk」
各ノード（超根含む）は必ず子の数だけ1、その後に0を1つ出力するので、出現順（BFS順）がそのままLOUDSノード番号になる。

3「k番目の1ビット」は子への辺
B中の1ビットは全て誰かの子を表す辺で、BFS全体で見ると子は生成順に並ぶためk番目の1ビットはノードk+1を指す。

4親の逆算
ノードxは親のエントリ中で(x-1)番目の1ビットとして生成された。その位置より前の0の個数が親のLOUDS番号になる。

よくあるミス

ミス	原因	正しい書き方
超根を省略して`B`を構築	「根には親がいないから不要」と誤解	超根の`"10"`を必ず先頭に付ける
LOUDS番号と実頂点番号を混同	番号体系が2つあることを見落とす	変換用の辞書を必ず経由する
`select1(x-1)`を`select1(x)`にしてしまう	オフセットの向きを逆にする	ノードxの親探索は「x-1番目の1ビット」
子の探索範囲の端点を間違える	半開区間の境界を誤る	開始`select0(x-1)+1`、終了`select0(x)`未満
子の出力順をLOUDS番号のまま出す	実頂点番号への変換を忘れる	実頂点番号に変換してからソート

次のステップ

発展: 本問のrank/selectは毎回$O(N)$の線形走査だが、Day145-Q3のJacobsonのブロック前計算と組み合わせればrankを$O(1)$、selectを$O(\log N)$に高速化できる。
次回予告: Farey数列の逐次生成（Stern-Brocot型mediant再帰によるソート・gcd不要の$O(|F_N|)$生成）

自己評価

完全理解おおむね理解要復習

Day 149-Q4 — LOUDS（Level-Order Unary Degree Sequence・簡潔木表現）

問題