No child can have descendants both to the left of x r and to the right of x r , because otherwise that child and x would be ill-nested.
we can split up the interval at x r to have two gap-minding trees, both rooted at p. The score of T is then the sum of the scores of the best subtree rooted at p over [i, k] (C[i, k, p]) and the score of the best subtree rooted at p over The above cases cover all non-empty gapminding trees, so the maximum will be found.