必要な操作回数は葉の個数 \(L\) と等しいです（ \(1\) 回の操作で葉は高々 \(1\) つ削除されること、各操作でそれぞれの葉へのパスを選択すると目標を達成することから）。また、パスを縮約する代わりに各 \(W_v\) の寄与を考えると、以下の問題と同値であることが分かります。

• \(N\) 頂点の頂点重み付き木が与えられる。葉に番号を付けて、 \(\{1,\ldots,L\}\) の順列 \(P\) について \(C_v\) を「部分木に含まれる葉 \(u\) のうち \(P_u\) の最大値」と定義する。 \(\sum_v W_v C_v\) の最大値と最小値を求めよ。

最大化

逆から考えると以下の貪欲が成立します。

• そのパスを取り除いても連結成分が増加しないような極大なパスで重み最小のもの（重みを \(S\) とする）を選んで除き、 \(i\) 回目の操作ならコストに \(i \times S\) を加える．

この貪欲を愚直に行うと \(O(N^2)\) かかりますが、各葉から伸びるパスをセグメント木などで管理すると \(O(N \log N)\) でシミュレーションできます。

最小化

取ってきたパスを全て連結するとトポロジカルソートになっていることに注目すると、以下の一般化された問題が出てきます。

• 長さ \(N\) の配列 \(A_v,B_v\) が与えられる。木のトポロジカルソート \(P\) について \(\sum_{i<j} A_{P_i}B_{P_j}\) を最小化せよ。

実際、\(A_v=W_v, B_v =\begin{cases} 1 & (vが葉のとき) \\ 0 & (otherwise) \end{cases}\)としたときの答えに適切なoffsetを足せばよいです。

これは01 on Treeのインスタンスです。アルゴリズムの挙動に注意すると葉からbottom-upにマージされることが分かるので、少し実装量を減らすことができます。

以上より、問題を \(O(N \log N)\) で解くことが出来ました。