Chapter 2 · Trees
Counting Trees: Cayley and Prüfer
n^(n-2) labelled trees, the bijection that proves it, and what the degree sequence looks like from the code.
The number of trees on the labelled vertex set {1, …, n} is nn-2.
Three proofs exist in the wild; only one is useful in a contest, because it also generates and decodes.
#The Prüfer code
Given a labelled tree, repeat until two vertices remain: output the label of the smallest leaf, delete it, and decrease the degree of its neighbour. The output is a sequence of n-2 numbers in [1,n].
The map above is a bijection between labelled trees on n vertices and all nn-2 sequences of length n-2 over [1,n].
Construct the inverse: given P = (p1, …, pn-2), set deg(v) = 1 + #{i : pi = v}. For i = 1 … n-2: let v be the smallest label with deg(v) = 1; emit the edge v → pi; set deg(v) := 0, deg(pi) := deg(pi) - 1. Finally connect the two labels that still have deg = 1. Well-defined: at each step the remaining degree sum is ∑ (1 + occurrences left) = (number of remaining vertices) + (remaining sequence length) = k + (k - 2) > k - 1, so at least two vertices have degree 1 — a leaf always exists. Round-trip: decoding rebuilds exactly the deletions in order, because both procedures pick "smallest vertex whose remaining degree is 1" at the same moments; encoding a decoded tree recovers P since each emitted edge's non-leaf endpoint is pi. Counting: n choices per position, n-2 positions. ∎
// encode: O(n log n) with a set of leaves
vector<int> prufer_encode(int n) {
multiset<int> leaves;
for (int v = 1; v <= n; v++) if (deg[v] == 1) leaves.insert(v);
vector<int> p;
vector<int> d = deg, par(n + 1);
set<int> alive;
for (int v = 1; v <= n; v++) alive.insert(v);
while ((int)p.size() < n - 2) {
int v = *leaves.begin(); leaves.erase(leaves.begin());
int u = neighbour_of(v); // the unique alive neighbour
p.push_back(u);
if (--d[u] == 1) leaves.insert(u);
alive.erase(v);
}
return p;
}#What the code makes trivial
Corollaries you can read off the sequence
- deg(v) = 1 + (number of times v appears in the code) — the standard solution to "reconstruct the tree from its degrees".
- Number of trees where vertices 1..k are leaves: sequences avoiding 1..k = (n-k)n-2.
- Number of spanning trees of Ka,b: ab-2 ba-2 — count sequences whose positions split by part, or use The Matrix–Tree Theorem.
- Probability a fixed vertex has degree d in a random tree: C(n-2, d-1) (1/n)d-1 (1-1/n)n-1-d — binomial, so degrees concentrate near 1.
- Rooted labelled trees: nn-1 (multiply by n choices of root). Ordered (plane) trees with n vertices: Catalan (1)/(n)C(2n-2, n-1) — a different object; don't mix them up.
Given degrees d1, …, dn with ∑ di = 2n-2, output any tree. Run the decode direction: push every vertex i exactly di - 1 times into a queue, keep a min-heap of "still has zero copies used and degree 1", attach greedily. O(n log n), and it is exactly Prüfer decoding with the multiset precomputed.
#When counting is modulo a prime
Contest versions ask for nn-2 mod p. Two cautions:
- n can be 109, so use fast power; if p is not prime, Euler's theorem needs gcd(n,p)=1.
- "Count trees with additional constraints" (degree upper bound, prescribed diameter) is usually not Prüfer-friendly except via generating functions: prescribe degrees exactly → multinomial ((n-2)!)/(∏ (di - 1)!).