関数グラフと構成 各頂点から の辺を張ると、すべての頂点の出次数が の関数グラフになる。各弱連結成分には有向閉路がちょうど一つあり、残りは閉路に向かう木となる。
長さ三以上の閉路では辺を一つ除き、残りを友人関係にする。長さ二の閉路は同じ二人の互いへの希望なので、無向辺を一つだけ残す。自己ループは捨て、閉路以外の辺はすべて残す。得られた森の成分を任意の辺でつなぐと木になる。
DSU で各 の両端が異なる集合のときだけ辺を追加して併合すれば、この構成が得られる。最後に頂点 とまだ異なる集合の頂点をつなぐ。
最適性の証明 の項は常に で、閉路外の自己ループでない希望の距離は少なくとも 。長さ の有向閉路を考える。任意の最終的な木で、閉路順に各頂点を訪れて出発点へ戻る経路をつなぐと、これらの頂点を含む最小部分木のすべての辺を少なくとも二度通る。この部分木には異なる 頂点があるため、辺数は少なくとも 。従って閉路の距離合計は 以上となる。他の成分の頂点を経由してもこの下界は変わらない。
構成では の閉路について、 個の希望の距離は 、除いた一つの距離は で、合計は 。長さ二なら両方の距離が となる。閉路外もすべて距離 である。成分を接続しても成分内部の唯一の経路は変化しないので、すべての下界を同時に達成する。
最小値は次の式である。
入次数 の頂点をキューで削除すると、閉路の頂点だけが残る。残った閉路を巡回して長さを数えれば、式を で計算できる。長さ二の閉路は一本の友人関係を共有するが、目的関数では二つの希望を別々に数える。
計算量と検証 構成の時間は 、空間は 。深さが になる場合もあるため参照コードは再帰 DFS を使わない。最小値は 以上 以下。不正な候補木の距離合計は最大 となり得るので、チェッカーでは符号付き ビット整数を使う。頂点番号、次数、深さは 以下である。
チェッカーは辺数、端点、木であることを検査し、LCA で実際の距離合計を計算して独立に求めた最小値と比較する。時間・空間は 。
サブタスク 1 は Prüfer 列で全 個のラベル付き木を列挙する。各木で全頂点から BFS を行うと で評価でき、全体の時間は 、空間は 以下。 なら十分である。サブタスク 4 は関数グラフと DSU を使う。
Solution written by GPT6