14,250,748,561 点解法 (https://atcoder.jp/contests/ahc007/submissions/27870652) の解説です。 かなり上級者向けです。

辺 \(i\) の長さ \(l_i\) を知った時点で、辺 \(i\) を使うべきかどうかを判定したいです。 もし、最適な戦略における使った場合の期待値と、使わなかった場合の期待値が計算出来れば、使うべきかどうか分かりますが、そのような計算を高速に行うことは難しそうです。そこで、まずは以下の簡単な場合を考えてみましょう。

\(u_i\) に接続する辺集合 \(\delta(u_i)\) から少なくとも1本は採用する必要があります。ちょうど1本採用する場合の最適な戦略は動的計画法により\(O(deg(u_i))\)時間で計算が可能です。辺 \(i\) を採用せず、残りの \(\delta(u_i) \setminus \{i\}\) から1本採用する場合の最適戦略の期待値を動的計画法により計算し、その値が \(l_i\) 以上であれば、その時点で辺 \(i\) を採用すると決めてしまうことが出来ます。

上記の手法は \(u_i\) と \(v_i\) を分割する任意の辺集合(\(u_i\)-\(v_i\) カット)に対して適用することが出来ます。採用した方が良いという判定に成功するためにはカットに含まれる辺の長さが長い方が良さそうなので、\(d_j\) 以上 \(3d_j\) 以下のランダムな値を辺 \(j\) に設定して\(\{u_i,v_i\}\) を始点としたPrim法を何度か走らせ、その途中で生成されたカット全てに対して、それぞれ判定を行いました。 ここまでで、14,226,312,641点が達成できました。

上記の方針を更に多分割カットへと拡張することが出来ます。 \(u_i\) を含む連結成分、\(v_i\) を含む連結成分、\(u_i\)も\(v_i\)も含まない連結成分の3つに分割するカットを考えます。すると、動的計画法により、これらを連結にするためにカットの中の辺を2本選ぶための最適戦略が求まり、辺 \(i\) を採用すべきかの判定が出来ます。 二分割の場合と同じようにPrim法を走らせる途中で生成された3分割カット全てについて判定を行ったところ、14,250,748,561点が達成できました。