TAOCP 2.3 Exercise 6
Two nodes `X` and `Y` of a tree are said to be _$m$th cousins, $n$ times removed_ if the following holds.
Exercise 6. ▶ [**] [21] Define the statement "X is an $m$th cousin of Y, $n$ times removed" as a meaningful relation between nodes X and Y of a tree, by analogy with family trees, if $m \ge 0$ and $n \ge 0$. (See a dictionary for the meaning of these terms in regard to family trees.)
Verified: no
Solve time: 36s
Two nodes X and Y of a tree are said to be $m$th cousins, $n$ times removed if the following holds. Let A be the nearest common ancestor of X and Y. Suppose the path from A to X passes through $p$ edges and the path from A to Y passes through $q$ edges, with $p \ge q \ge 1$. Then X and Y are $m$th cousins, $n$ times removed if $m = \min(p, q) - 1$ and $n = |p - q|$. In other words, the cousin number $m$ is one less than the number of generations from the common ancestor to the nearer node, and the removal number $n$ is the difference in generations from the common ancestor to the two nodes. This definition agrees with the standard terminology used in family trees, where siblings correspond to $0$th cousins, first cousins share a grandparent, and so on.