Day 132-Q1 | Prüfer列（木とラベル付き数列の全単射）

問題

$1$から$N$までのラベルが付いた木を考える。この木のPrüfer列とは、「葉（次数1の頂点）のうちラベルが最小のものを選び、その唯一の隣接頂点のラベルを数列に記録してから、その葉を木から取り除く」という操作を頂点が2個になるまで繰り返して作られる長さ$N-2$の数列である。

Prüfer列 $a_1,\dots,a_{N-2}$ が与えられたとき、これを生成した木を復元し、辺集合を出力せよ（Prüfer列⇔木は全単射なので木は一意に定まる）。

入力形式

N
a_1 a_2 ... a_{N-2}

制約

$3 \le N \le 2\times10^5$

$1 \le a_i \le N$

入力は必ずある木のPrüfer列として妥当

入出力例

入力例1

6
4 4 4 5

出力例1

辺は $u<v$ となるように $(u,v)$ で1行ずつ、$(u,v)$の辞書順昇順に出力する。

概念図

ヒント（段階的開示）

ヒント1（方向性）

Prüfer列の定義を素朴に逆再生しようとすると、「現在の木の葉集合」を毎回維持する必要がある。木を明示的に構築・破壊するとO(N²)になるので、次数配列と優先度付きキューだけで「今どの頂点が葉か」を管理する方法を考える。

ヒント2（アプローチ）

頂点$v$がPrüfer列中に出現する回数を$c_v$とすると、木における$v$の次数は$c_v+1$に等しい。この事実だけで木を作らずに次数配列を計算できる。次数1の頂点を最小ヒープに入れ、数列を先頭から読みながら「ヒープの最小葉」と「今読んだ数字」を結ぶ辺を確定させ、関係する頂点の次数を更新する。読了後、未使用の2頂点を最後に直結する。

ヒント3（誘導）

import heapq

def decode(n, seq):
    degree = [1] * (n + 1)
    for x in seq:
        degree[x] += 1
    leaves = [v for v in range(1, n + 1) if degree[v] == 1]
    heapq.heapify(leaves)
    used = [False] * (n + 1)
    edges = []
    for x in seq:
        leaf = heapq.heappop(leaves)
        edges.append((min(leaf, x), max(leaf, x)))
        used[leaf] = True
        degree[x] -= 1
        if degree[x] == 1 and not used[x]:
            heapq.heappush(leaves, x)
    remain = [v for v in range(1, n + 1) if not used[v]]
    a, b = remain
    edges.append((min(a, b), max(a, b)))
    return sorted(edges)

模範解答 (Python)

import sys
import heapq

def solve():
    data = sys.stdin.read().split()
    idx = 0
    n = int(data[idx]); idx += 1
    seq = [int(data[idx + k]) for k in range(n - 2)]
    idx += n - 2

    degree = [1] * (n + 1)
    for x in seq:
        degree[x] += 1

    leaves = [v for v in range(1, n + 1) if degree[v] == 1]
    heapq.heapify(leaves)

    used = [False] * (n + 1)
    edges = []
    for x in seq:
        leaf = heapq.heappop(leaves)
        edges.append((min(leaf, x), max(leaf, x)))
        used[leaf] = True
        degree[x] -= 1
        if degree[x] == 1 and not used[x]:
            heapq.heappush(leaves, x)

    remain = [v for v in range(1, n + 1) if not used[v]]
    a, b = remain[0], remain[1]
    edges.append((min(a, b), max(a, b)))

    edges.sort()
    out = []
    for u, v in edges:
        out.append(f"{u} {v}")
    print("\n".join(out))

solve()

Step-by-Step 解説

1次数を木を作らずに求める
頂点$v$がPrüfer列に出現する回数$c_v$は「$v$から取り除かれた葉の本数」に等しい。よって`degree[v]=c_v+1`が成り立つ。

2最小葉ヒープでシミュレーション
次数1の頂点をヒープで管理し、数列を読みながら最小の葉と現在値を結ぶ。相手の次数を減らし1になればヒープへ追加。

3最後の1本
数列処理後、一度も葉になっていない頂点が2個残る。これらを直結して最後の辺とする。

4計算量
ヒープ操作は最大N回・各O(log N)で全体O(N log N)。出力ソートも同様。

5背景
この全単射はラベル付き木の総数=$N^{N-2}$というCayleyの公式の構成的証明でもある。

よくあるミス

ミス	原因	正しい書き方
次数配列を`degree[v]=c_v`（+1忘れ）で計算	葉は最初から次数1という初期条件を忘れる	全頂点を`[1]*(n+1)`で初期化してから出現回数を加算
木を実際に構築・削除しO(N²)になる	葉集合の管理を全頂点走査で行う	次数配列+最小ヒープだけで暗黙に葉集合を管理
最後の1本の辺を忘れる	ループはN-2回しか回らない	未使用頂点2個を最後に直結する処理を追加
使用済み頂点を重複してヒープに積む	`used[x]`チェック漏れ	`degree[x]==1 and not used[x]`の両方を確認してからpush

次のステップ

発展: 木からPrüfer列へのエンコードも同じ最小葉ヒープ構造でO(N log N)実装できる。往復一致を確認すると理解が深まる。
発展2: 次数列を指定したランダム木生成への応用
次回予告: 次回のテーマは今後のセッションで選定

自己評価

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

Day 132-Q1 — Prüfer列（木とラベル付き数列の全単射）

問題