Neighbor joining builds a phylogenetic tree from a distance matrix, and its key insight is that
you must not simply merge the closest pair: a taxon on a long branch looks far from everything, so
raw distance is misleading. The Q-matrix corrects each distance by how far both taxa are from
everyone else, which is what makes the method statistically consistent.
Statement
Given a symmetric distance matrix over n taxa, determine which pair neighbor joining merges
first.
Neighbor joining does not pick the smallest distance. It computes, for every pair i != j:
Q(i,j) = (n - 2) * d(i,j) - sum(d(i,k) for all k) - sum(d(j,k) for all k)
and merges the pair with the smallest Q(i,j).
The first line holds n. The next n lines each hold n space-separated numbers — row i of
the distance matrix. Taxa are numbered 1 to n in matrix order.
Print the two taxon numbers of the first pair to merge, space-separated and in increasing order.
If several pairs tie for the smallest Q, print the one with the smallest first number, then the
smallest second number.
Input — read from standard input
| Variable | Type | Description |
|---|---|---|
n
line 1
|
int |
The number of taxa
3 <= n <= 20
|
matrix_rows
line 2
|
list[str] |
The n rows of the distance matrix, each n space-separated numbers
symmetric, zero on the diagonal, non-negative
|
These variables are already read for you in the starter code on the right.
Output
str the two taxon numbers of the first pair to merge, increasing order
Sample Cases
4
0 5 9 9
5 0 10 10
9 10 0 8
9 10 8 0
1 23
0 1 2
1 0 3
2 3 0
1 2Submit also runs your code against 4 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
3 <= n <= 20- The matrix is symmetric with zeros on the diagonal
- Ties are broken by smallest first index, then smallest second index
- Taxa are numbered from
1, in the order the matrix rows are given
Further Reading
- Compute each row's total distance once and reuse it — that's the
sum(d(i,k))term. - Iterate
i < jin increasing order and keep a strict<comparison, and the tie-break falls
out naturally.