Add-pruneの新しいアルゴリズムを考える。

$n$: number of taxa $N$: number of trees $m$: number of bipartitions

案1

アイディア：基本的にはaddの時はナイーブに計算をする。ただ、addを続けてやる場合は計算を節約できる場合がある。これを使う。

まずはずっとremoveする。（greedy pruningと同じ）-> tree $T_1$
removeが終わった後に、以下の操作をする。
- 各input_treeの各bipartitionに対して、
- $T_1$とのbest matchの値を計算
- 全てのinput_treeとのfirst L match を計算
- もし全てのinput_treeに対して、L番目のmatchよりも$T_1$とのbest matchの方が距離が近ければ、$T_1$とのbest matchより小さい距離を持つmatchesのbipartitionを保存する。
- そうでなければ、recompute flagを立てる。
- この時、同時にaddのメリットも計算できる。
addのメリットの一番大きいbipartitionを追加する。
次のiterationからもaddだけ考える。この時、計算を省略できる。
- recompute flagが立っているものは計算し直す (hamming dist?)
- そうでないものはmatchesの情報から計算ができる。
addが終わったらまたremoveに戻る。

recompute flagが頻繁に立つようであればかなり非効率的。
最大のスペースがかなり大きくなりそう。大きくなりそうな構造：
- T_1 と bipars の best match: O(n * m)
- bipars同士のfirst L match: O(L N m) ~ O(LnN^2) <- 実際は L*N の部分を小さくできそう。