Labeled Trees and Prufer Code
A Prüfer code gives a one-to-one correspondence between labeled trees on vertices and sequences of length whose values are between and .
This correspondence gives Cayley's formula immediately: the number of labeled trees is
It also provides practical algorithms for encoding, decoding, generating, and counting trees with degree restrictions.
We are given and a Prüfer sequence of length . Reconstruct the unique labeled tree.
To encode a tree, repeatedly remove its smallest leaf and append that leaf's neighbor to the sequence. After removals, two vertices remain.
A vertex appears in the Prüfer sequence exactly
times. Therefore, during decoding, initialize
The smallest vertex with degree one is the next removed leaf. Connect it to the next sequence value , decrease both degrees, and if becomes a leaf, add it to the leaf set. At the end, connect the last two leaves.
A min-priority queue keeps the current smallest leaf.
Algorithm:
Every queue operation costs .
The sequence tells us the neighbor of each leaf removed by the encoding process. The degree counts tell us when a label has stopped appearing and is ready to become a leaf itself.
Decode for .
Because every length- sequence is valid and decodes to exactly one tree, and every tree has exactly one code, there are labeled trees.
The input contains and then integers. For , the sequence is empty.
1. Set every degree to 1.
2. For each x in the Prüfer sequence, increase degree[x].
3. Put every vertex of degree 1 into a min-priority queue.
4. For each x in the sequence:
1. Remove the smallest leaf.
2. Add edge leaf-x.
3. Decrease degree[leaf] and degree[x].
4. If degree[x] becomes 1, put x into the queue.
5. Remove the last two leaves and connect them.
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
void solve() {
int n;
cin >> n;
vector<int> prufer(max(0, n - 2));
vector<int> degree(n + 1, 1);
for (int &x : prufer) {
cin >> x;
degree[x]++;
}
priority_queue<int, vector<int>, greater<int>> leaves;
for (int v = 1; v <= n; v++) {
if (degree[v] == 1) {
leaves.push(v);
}
}
vector<pair<int, int>> edges;
for (int x : prufer) {
int leaf = leaves.top();
leaves.pop();
edges.push_back({leaf, x});
degree[leaf]--;
degree[x]--;
if (degree[x] == 1) {
leaves.push(x);
}
}
int v = leaves.top();
leaves.pop();
int u = leaves.top();
edges.push_back({v, u});
for (auto [a, b] : edges) {
cout << a << ' ' << b << '\n';
}
}
int32_t main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
solve();
return 0;
}