We use induction to give a proof that S[i][j] = max T e i ∈T w i after running our algorithm, where T is a set of tree nodes that satisfies T ∈ T i and e i ∈T l i = j. , then the set is contained in T lo(i) , and its size is j.
the maximum weight equals S[lo(i)][j] (Alg.1 line 9).