Day 146-Q3 | Cole-Vishkinアルゴリズム

問題

$N$頂点の根付き木が与えられる（頂点1が根）。各頂点$v$の初期色を$\text{color}(v)=v$とする（相異なるためproper coloring）。

次の縮小ステップを、色の種類数が$6$以下になるまで繰り返す。根以外の全頂点$v$（親$p(v)$）について、ステップ開始時点の$a=\text{color}(v)$，$b=\text{color}(p(v))$を用い:

$a,b$を2進数表現し、最下位ビットから見て最初に異なるビット位置$i$を求める。
$a$のビット$i$の値を$b_i$とする。
新色を$\text{newcolor}(v)=2i+b_i$とする。

全頂点の新色を同時に確定させる（根は更新しない）。

求めるもの: 色の種類数が6以下になるまでのラウンド数と、そのときの全頂点(1〜N)の色。

入力形式

N
p_2 p_3 ... p_N

制約

$2 \le N \le 30$

$1 \le p_i < i$

入出力例

入力例1

8
1 1 2 2 3 3 4

出力例1

1
1 0 3 2 1 0 5 4

初期色1..8（8色）が1ラウンドで色集合{0,1,2,3,4,5}の6色ちょうどに収束する。

概念図：1ラウンドでの彩色数縮小

ヒント（段階的開示）

ヒント1（方向性）

隣接頂点の色が異なることを保ったまま色の総数を大きく減らすには、「なぜ2色は異なるのか」という理由そのもの（2進数表現で最初に異なるビット位置とその値）を新しい色として使う発想が鍵。

ヒント2（アプローチ）

新色$\text{newcolor}(v)=2i+b_i$が親子間で異なることを保証するには、$v$と$p(v)$それぞれの「自分の色と自分の親の色（更新前）」だけを比較すればよい。両者が選ぶビット位置$i$が同じでもビットの値は互いに反転しているため衝突しない。

ヒント3（誘導）

def reduction_step(colors, parent):
    N = len(colors)
    new_colors = colors[:]
    for v in range(2, N + 1):
        a = colors[v - 1]
        b = colors[parent[v] - 1]
        i = 0
        while ((a >> i) & 1) == ((b >> i) & 1):
            i += 1
        bit = (a >> i) & 1
        new_colors[v - 1] = 2 * i + bit
    return new_colors

`len(set(colors))`が6以下になるまで繰り返す。毎回コピーしてから更新し「同じステップ内は全員旧色を参照」を保つこと。

模範解答 (Python)

import sys

def main():
    data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(data[idx]); idx += 1
    parent = [0] * (N + 1)
    for i in range(2, N + 1):
        parent[i] = int(data[idx]); idx += 1

    colors = [v for v in range(1, N + 1)]

    rounds = 0
    while len(set(colors)) > 6:
        new_colors = colors[:]
        for v in range(2, N + 1):
            a = colors[v - 1]
            b = colors[parent[v] - 1]
            i = 0
            while ((a >> i) & 1) == ((b >> i) & 1):
                i += 1
            bit = (a >> i) & 1
            new_colors[v - 1] = 2 * i + bit
        colors = new_colors
        rounds += 1

    print(rounds)
    print(' '.join(map(str, colors)))

main()

Step-by-Step 解説

1初期状態は必ずproper coloring
頂点番号は相異なるため任意の親子ペアも異なる色を持つ。

21ラウンドの更新（同期性が本質）
全頂点を同時に（更新前の値を参照して）処理する。逐次的に更新すると理論保証が崩れる。

3色数が急減する理由
元の色が$W$ビットなら新色は$0$〜$2W-1$の範囲、これは$\lceil\log_2(2W)\rceil$ビットで表現できる。$W\to\log W$の縮小を繰り返すと$\log^\ast N$ラウンドで定数に落ちる。

4入力例の検証
$N=8$の木で1ラウンド適用すると色集合が$\{0,1,2,3,4,5\}$の6色ちょうどになり停止。

5さらに3色へ（発展・理論のみ）
6色到達後、色の大きい頂点から周囲で未使用の小さい色に「格下げ」する後処理でさらに3色まで落とせる。

よくあるミス

ミス	原因	正しい書き方
ラウンド内で更新した色を同ラウンドの別頂点の計算に使う	配列をその場で書き換える	別配列を用意しラウンド終了後に一括反映
根の色も更新しようとしてエラーになる	ループ範囲を`range(1,N+1)`にする	根は除外し`range(2,N+1)`とする
最初に異なるビット位置の探索で無限ループ	$a=b$のケースを想定	問題前提より$a\ne b$は常に保証される
停止条件を「色の最大値が6未満」で判定	種類数と最大値を混同	`len(set(colors))`で種類数を数える
ビット位置の探索方向を逆にする	最上位ビットから探すと誤解	定義通り最下位ビットから探索する

次のステップ

発展: 6色から3色への後処理フェーズを実装し、最終的に3色で塗り分けられることを確認せよ。
次回予告: Efraimidis-Spirakis法（重み付きReservoir Sampling・A-Res algorithm）

自己評価

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

Day 146-Q3 — Cole-Vishkinアルゴリズム（森の彩色数縮小・決定的対称性破壊）

問題