https://kyopro.hateblo.jp/entry/2019/01/16/200456

ラベル付き木から prüfer sequence（プリューファ列）と呼ばれる整数列への一対一対応を説明します．

ラベル付き木

ここでは各頂点のラベルが $1$ から $n$ の値が付いた $n$ 頂点のラベル付き木を考えます．下の図は頂点数 $2, 3, 4$ の非同型なラベル付き木の例です（画像：Cayley's formula - Wikipedia）．ラベルなし木とは異なることに注意してください．

f:id:tatanaideyo:20190116161300p:plain:w250 — Wikipedia: Cayley's formula

Prüfer sequence

各ラベル付き木に対して Prüfer sequence と呼ばれる整数列が一対一対応します．まず初めにラベル付き木から Prüfer sequence への変換方法を示して，その後で Prüfer sequence からラベル付き木への逆変換を示します．

ラベル付き木　👉　Prüfer sequence

頂点数 $n$ のラベル付き木 $T$ から長さ $n - 2$ の Prüfer sequence $p = (p_1, p_2, \ldots, p_{n-2})$ への変換を説明します．ラベル最小の葉に隣接する頂点を Prüfer sequence に加えて，その葉を削除するということを Prüfer sequence のサイズが $n - 2$ になるまで繰返します．頂点数が $2$ 以上ならば葉が存在して，葉の次数は1であることから隣接する頂点は一意に定まります．
擬似コードと C++ のソースコードを下に載せます． C++ のソースコードの実行時間は $O(n \log n)$ です．

1.　 $T_1 = T$ とする
2.　 $i = 1$ から $i \le n - 2$ まで次を繰り返す
　　2-1.　 $T_i$ からラベルの値が最小となる葉 $v \in V(T_i)$ を選ぶ
　　2-2.　 $v$ に隣接する頂点を $u \in V(T_i)$ として， $p_i = u$
　　2-3.　 $T_{i + 1} = T_i - v$

C++ のソースコードを表示

#include <iostream>
#include <vector>
#include <queue>

struct Graph {
    size_t n;
    std::vector<std::vector<int>> adj;

    Graph(size_t _n) : n(_n), adj(_n) {}
    void add_edge(const int u, const int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
};

std::vector<int> TreeToPruferSequence(const Graph &tree) {
    if (tree.n <= 2) return std::vector<int>{};

    std::priority_queue<int, std::vector<int>, std::greater<int>> que;
    std::vector<int> deg(tree.n);
    for (size_t v = 0; v < tree.n; ++v) {
        deg[v] = tree.adj[v].size();
        if (deg[v] == 1) que.push(v);
    }

    std::vector<int> seq; seq.reserve(tree.n - 2);
    while (seq.size() + 2 < tree.n) {
        const int leaf = que.top(); que.pop();
        for (int u : tree.adj[leaf]) {
            if (deg[u] != 0) {
                seq.push_back(u);
                --deg[u];
                if (deg[u] == 1) que.push(u);
                break;
            }
        }
        --deg[leaf];
    }

    return seq;
}

int main() {
    std::cin.tie(0); std::ios::sync_with_stdio(false);

    int n;
    std::cin >> n;

    Graph tree(n); // ラベルは 0 から n - 1
    for (int i = 0, u, v; i < n; ++i) {
        std::cin >> u >> v;
        tree.add_edge(u, v);
    }

    auto prufer_sequence = TreeToPruferSequence(tree);
    for (const auto &x : prufer_sequence) std::cout << x << '\n';

    return 0;
}

例）頂点数 $9$ のラベル付き木

下のラベル付き木の prüfer sequence は $(4, 4, 2, 3, 3, 3, 4)$ です．また，取り除いていく頂点は順番に $1, 5, 6, 2, 7, 8, 3$ です．
　　　　　　 f:id:tatanaideyo:20190116195313p:plain:w300

Prüfer sequence　👉　ラベル付き木

次に長さ $n - 2$ の prüfer sequence $p = (p_1, p_2, \ldots, p_{n - 2})$ から頂点数 $n$ のラベル付き木 $T$ への変換を説明します．各頂点 $v \in V(T)$ に対して， $p$ での $v$ の出現回数に1を足した値は $v$ の次数に等しくなります．疑似コードど C++のソースコードを下に載せます．C++の実行時間は $O(n \log n)$ です．
この変換は上の変換の逆変換となるので，これらの変換は一対一対応となります．

1.　 $(d_1, \ldots, d_n)$ を頂点 $i$ の次数を $d_i$ とする
2.　 $i = 1$ から $i \le n - 2$ まで次を繰り返す
　　2-1.　 $d_v = 1$ となるラベル最小の頂点 $v$ を求める
　　2-2.　頂点 $v$ と $p_i$ の間に辺を加える
　　2-3.　 $d_v$ と $d_i$ の値を1減らす
3.　 $d_u \neq 0, d_v \neq 0$ となる頂点 $u$ と $v$ の間に辺を加える

C++ のソースコードを表示

#include <iostream>
#include <vector>
#include <queue>

struct Graph {
    size_t n;
    std::vector<std::vector<int>> adj;

    Graph(size_t _n) : n(_n), adj(_n) {}
    void add_edge(const int u, const int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
};

Graph PruferSequenceToTree(const std::vector<int> seq) {
    const int n = seq.size() + 2;
    std::vector<int> deg(n, 1);
    for (const int v : seq) ++deg[v];

    std::priority_queue<int, std::vector<int>, std::greater<int>> que;
    for (int v = 0; v < n; ++v) if (deg[v] == 1) que.push(v);

    Graph tree(n);
    for (const int v : seq) {
        const int u = que.top(); que.pop();
        tree.add_edge(v, u);
        --deg[v]; --deg[u];
        if (deg[v] == 1) que.push(v);
    }

    const int lst = que.top(); que.pop();
    tree.add_edge(lst, que.top());

    return tree;
}

int main() {
    std::cin.tie(0); std::ios::sync_with_stdio(false);

    int size;
    std::cin >> size;

    std::vector<int> prufer_sequence(size);
    for (auto &&v : prufer_sequence) std::cin >> v;

    auto tree = PruferSequenceToTree(prufer_sequence);
    std::cout << "#vertices: " << tree.n << '\n';
    for (size_t v = 0; v < tree.n; ++v) {
        std::cout << v << ": ";
        for (auto u : tree.adj[v]) std::cout << u << " ";
        std::cout << '\n';
    }

    return 0;
}

例） prüfer sequence $p = (4, 4, 2, 3, 3, 3, 4)$

$p$ での各頂点の出現回数は $(0, 1, 3, 3, 0, 0, 0, 0, 0)$ なので各頂点の次数は $(1, 2, 4, 4, 1, 1, 1, 1, 1)$ となり， $p$ の長さが $7$ なので頂点数は $9$ となります． $p$ に対応するラベル付き木は上の図の木です．

応用問題

ケイリーの公式：Heinz Prüfer (1918)

$n$ 頂点のラベル付き木の個数が $n^{n - 2}$ であることをケイリーの公式と言います．ここでは，prüfer sequence を用いてケイリーの公式の証明を行います．
上の変換は一対一対応となっていたので， $n$ 頂点のラベル付き木全体とサイズ $n - 2$ の prüfer sequence の全体のサイズは等しくなります．長さ $n - 2$ の prüfer sequence の各要素は $1$ から $n$ までの $n$ 通りの選び方があるので，全体で $n^{n-2}$ 通りあります．したがって， $n$ 頂点のラベル付き木の数は $n^{n - 2}$ です．
ケイリーの公式は頂点数 $n$ のラベル付き完全グラフの全域木の数が $n^{n - 2}$ 個であることと同値です．

ケイリーの公式の発展版

頂点数 $n$ のラベル付き完全グラフ $K_n$ の全域木で，各頂点 $v$ の次数が $d_v$ となるものの数を求めます．
長さ $n - 2$ の prüfer sequence で考えます．上の prüfer sequence からラベル付き木への変換で述べたとおり，頂点 $v$ の次数は prüfer sequence での $v$ の出現回数に1を足した値と等しくなります．したがって，prüfer sequence に頂点 $v$ は $d_v + 1$ 回表れます．よって，求める数は，
　　　 $\frac{(n - 2)!}{(d_1 - 1)! (d_2 - 1)! \cdots (d_n - 1)! }$
となります．

ランダムなラベル付き木の生成

頂点数 $n$ のラベル付き木を確率 $\frac{1}{n^{n-2}}$ で生成することを考えます．
長さ $n - 2$ の prüfer sequence の各成分を独立に $\frac{1}{n}$ の確率で $1$ から $n$ の値を割り当てます．このとき， prüfer sequence が生成される確率は一様に $\frac{1}{n^{n - 2}}$ となります．これをラベル付き木に変換することによって一様ランダムなラベル付き木を生成することができます．
この方法はランダムなラベルなし木を生成しないことに注意してください．例えば，頂点数 $4$ のラベル付き木は全部で 16個あり下の図のようになります．このとき，ラベルなし木は上の12個が同型となり，また下の4個も同型となるので 2個しかありませんので，確率 $1 / 2$ で上のタイプか下のタイプを出力して欲しいのですが，ここでの生成方法では上のタイプは確率 $3 / 4$ で生成されてしまうので偏りが生じてしまいます．