UPGMA builds a rooted tree by repeatedly joining the two closest clusters and
averaging their distances to everything else. It assumes a molecular clock — a constant rate of
evolution along every lineage — which is often violated in real data, but it remains the clearest
introduction to distance-based phylogenetics and is still used for quick exploratory trees and for
clustering in immunology and microbiome work.
Statement
You are given a symmetric distance matrix over n taxa labelled 0 to n-1.
Build a UPGMA tree by repeatedly merging the two clusters with the smallest distance between them. When
clusters A and B merge, the distance from the new cluster to any other cluster C is the weighted
average:
d(AB, C) = (|A| * d(A,C) + |B| * d(B,C)) / (|A| + |B|)
where |A| is the number of taxa in cluster A.
For each merge, in the order the merges happen, print a line containing the two cluster identifiers
merged and the distance between them, formatted as i j d with d to four decimal places. Print
the smaller identifier first. New clusters are numbered n, n+1, and so on in merge order.
On ties, merge the pair with the smallest first identifier, then the smallest second identifier.
Input — read from standard input
| Variable | Type | Description |
|---|---|---|
n
line 1
|
int |
The number of taxa
2 <= n <= 30
|
matrix
line 2..n+1
|
str |
An n x n symmetric distance matrix, one row per line, space separated
distances are non-negative numbers, diagonal is zero
|
These variables are already read for you in the starter code on the right.
Output
str one line per merge, two cluster ids and the merge distance to four decimal places
Sample Cases
4
0 2 4 6
2 0 4 6
4 4 0 6
6 6 6 0
0 1 2.0000
2 4 4.0000
3 5 6.0000
2
0 5
5 0
0 1 5.0000Submit also runs your code against 3 hidden test cases. Hidden inputs are never shown — if one fails you'll get its number and a description of the mismatch, not the data.
Constraints
2 <= n <= 30- The input matrix is symmetric with a zero diagonal
- Exactly
n - 1merges occur - Ties resolve to the smallest first identifier, then the smallest second identifier, making output unique
Further Reading
- Track active cluster identifiers and their sizes in parallel with the distance map.
- Use a dictionary keyed by frozen pairs, or a dictionary of dictionaries, so removing merged clusters
is straightforward. - Scan candidate pairs in ascending identifier order so the tie-break falls out naturally.