\(f(i,j)\) を高速に求める方法を考えます．

まず，union-find の過程を表した根付き二分木 \(U\) を用いて \(G\) の構造を表現することにします． 具体的には，\(U\) にはちょうど \(N\) 個の葉と，\(N-1\) 個の内部頂点があります．葉はそれぞれが \(G\) の頂点に対応します． 各内部頂点 \(k\) には重み \(w_k\) が定まっています． 葉 \(i,j\) の LCA を内部頂点 \(k\) とすると，\(G\) で \(i,j\) を結ぶ辺の容量は \(w_k\) です．

\(G\) 上で \(i,j\) を分離する最小カットの構造について考えます． 実は，以下の性質が成り立ちます．

• \(U\) の辺 \(e\) を切ると二つの木が得られる．このうち根を含まない方の木に含まれる葉の集合を \(X_e\)，根を含む方の木に含まれる葉の集合を \(Y_e\) とする．ここで，ある \(e\) が存在して，\(X_e,Y_e\) が \(i,j\) 間の最小カットを与える．

この性質を認めれば，問題を解くのは簡単です． \(U\) の各辺 \(e\) に対してそれに対応するカットのコストを計算し，その辺の重みとします． \(f(i,j)\) は，\(U\) の葉 \(i,j\) の間のパスの辺の重みの最小値です． 全ペアに対してこの値を集計するのは union-find で行えます． 計算量は \(O(N \log N)\) です．

解答例(C++)

最後に，上述の性質を証明しておきます．

\(G\) 上の \(i,j\) カットを \((I,J)\) とします． \(i \in I, j \in J\) です． 葉 \(i,j\) の LCA を \(k\) とします． \(k\) の子のうち，\(i\) を含む方を \(X\)，\(j\) を含む方を \(Y\) とします． \(k\) の部分木以外の頂点を \(Z\) とします． \(X\) 内にある葉であって \(I\) に含まれるものを \(X_I\) とします． 同様に，\(X_J,Y_I,Y_J,Z_I,Z_J\) も定義します．

ここで，一般性を失わず，\(|X_I| \leq |Y_J|\) とします．ここで，\((X_I,X_J \cup Y_I \cup Y_J \cup Z_I \cup Z_J)\) というカットを考えます． つまり，\(Y_I \cup Z_I\) を \(i\) 側から \(j\) 側へ移動させた後のカットです． このカットの容量が元のカットの容量以下であることが示せます． ここで重要になるのは，\(U\) において，内部頂点の重みは，根に近づくほど小さくなるという点です． これを念頭に置くと，\(Y_I\) の移動による”得”（カットの容量の減少量）は，最低でも \(|Y_I| \times (|Y_J|-|X_I|) \times w_k\) であり，これが \(0\) 以上です． \(Z_I\) の移動について考えると，コストを決定する内部頂点が全部 \(k\) の先祖なので，\(X_I\) と \(Y_J\) の頂点数だけが重要になり，やはり得は \(0\) 以上とわかります． これらを合わせることで，新しいカットの容量が元のカット以下であることが示せます．

以上より，最適なカットであって \(Y,Z\) をすべて \(j\) 側に置くようなものが存在するとわかるので，これを一つとります．

次に，\(i\) 側のカットの全頂点の LCA を \(h\) と置きます． ここで，\(j\) は \(h\) の部分木の外にあります． \(h\) の子のうち \(i\) を含むものを \(X\)，含まないものを \(Y\)，\(h\) の部分木外を \(Z\) と置き，\(X_I,X_J,Y_I,Y_J,Z_J\) を前セクションと同様に定義します．\(Z_I\) は空なので使いません．

ここで，以下の二つのカットを考えてみます．

• \((X_I,X_J \cup Y_I \cup Y_J \cup Z_J)\)
• \((X_I \cup X_J \cup Y_I \cup Y_J, Z)\)

これら \(2\) つのカットの容量と，元のカットの容量の差分を考えます． まず，\(Z_J\) 外の葉 \(v\) に対し，\(v\) と \(Z_J\) 内のすべての頂点との間の辺の容量の総和を考えると，これは \(v\) によらず一定です． この値を \(R\) と置くことにします．

\(1\) つめのカットについて考えます．これは \(Y_I\) を \(j\) 側に移動したカットです． この移動による得は，\(((|X_J|+|Y_I|-|X_I|)\times w_h+R) \times |Y_I|\) 以上です．

次に \(2\) つめのカットについて考えます． これは \(X_J,Y_J\) を \(i\) 側に移動したカットです． この場合の得は \(((X_I+Y_I)\times w_h-R) \times (|X_J|+|Y_J|)\) 以上です．

これら \(2\) つの値が両方とも負ということはありえません． \(2\) つめのカットで \(0\) 以上得できる場合，探していた形のカットが得られたことになります． \(1\) つめのカットで \(0\) 以上得できる場合，\(h\) がより葉に近いカットが得られることになり，これを続けていけば，いずれは目標の形のカットにたどり着きます．

よって証明ができました．