In the i-th iteration we add e = (u, v) to T i , and remove the lostArcs from E. Every lost arc participates in O(n k−1 in ) parts, and we need to update O(k) entries for each lost part in DS(a) (as the value of the other arcs of that part should no longer account for that part's weight) and O(k 2 ) entries in DS (b).
the total update time of the DSs is O(n k in × k 2 ) and the total runtime of Algorithm 2 is O(n k+1 in × k + n × (n × n in × (n in + min{n 2 in , n k−1 in })+n k in ×k 2 )).