Official

D - Sum of Maximum Weights Editorial by KoD


以下では、辺の重みは相異なると仮定します。制約にそのような条件はありませんが、添字の大小による tie-break などを行えばよいです。

\(i \, (1 \leq i \leq N -1)\) について、\(f(u, v) = w_i\) となる \((u, v)\) の総数を数えることを考えます。\(f(u, v) = w_i\) となるための条件は、頂点 \(u, v\) を結ぶパスに辺 \(i\) が含まれ、かつそのパスに含まれる他の辺の重みが \(w_i\) より小さいことです。

重みが \(w_i\) より小さい辺のみを張ったグラフを考えると、これは森(グラフ理論の用語)となっており、\(u_i\)\(v_i\) は必ず異なる連結成分に属します。これら二つの連結成分の一方に \(u\)、もう一方に \(v\) が属することが、\(f(u, v) = w_i\) となるための条件です。

よって、辺の重みの小さい順にグラフに追加していき、Union-Find などのデータ構造を用いて連結成分の大きさを取得することにより 、この問題を解くことができます。

実装例 (C++)

posted:
last update: