概要
公式解説が読み解けておらず…。
木の圧縮パートを除くと大差ないかもしれません。なかなか実装が大変になってしまいました。
解法
グラフの変形
葉を縮約していきます。葉に接続する辺の寄与は、その両側にいくつの頂点があるかが分かれば計算できるので、それを答に足していきます。
葉に接続する辺の寄与を処理し終わっても、頂点を完全に削除してはダメです。辺を重み
この操作の結果、
特別な頂点
葉を縮約してしまうと、次数
そうでない場合、連結性よりすべての頂点の次数は
頂点や辺の個数を
なお、
グラフ全体としては、特別な頂点
- パスは
個 - パスの長さの和は
となります。頂点は、「特別な頂点」「パスの内点」の
葉を圧縮した関係で、
特別な頂点同士の距離
事前にパスを列挙しておいて、その距離をまとめて計算してしまうことで、Dijkstra 法などにより全点対最短距離が
特別な頂点と、パスの内点の距離の計算
パスの両端点から、注目している特別な頂点までの距離は、事前計算されています。すると、パスの内点から特別な頂点までの距離も、計算できます(パスのどちら側に進むかに応じて、
パスの内点は全部で
累積和によって計算量を落とすことも可能です(全体の計算量オーダーには影響しませんが、定数倍改善になるでしょう)。
同じパスの内点同士の距離
同じパスの内点同士であっても、最短路はそのパスの外側を通る可能性があるので、多少厄介です。
パスの長さを
- すべての
に対する、 の和を求めよ。
これを例えば
よって、「同じパスの内点同士の距離」の寄与は、長さ
異なるパスの内点同士の計算
それぞれのパスの長さを、
に対して の和を求めよ
この係数は、
あるパスに対して、相手のパスと
ひとつのパスの寄与は
コメント
最近解いた問題:https://atcoder.jp/contests/pakencamp-2018-day2/tasks/pakencamp_2018_day2_g
と似たところが問われている問題。私は本記事の問題の方が、苦戦しました。
どちらも何らかの手法でグラフを圧縮することになりますが、解説の手法?(ちゃんと定義されていないように見えるが、木に追加する辺の端点や、その部分集合の LCA として書ける頂点を特別視かな?)と比べて、私の試みた葉やパスの縮約の方が、頂点数が少なく抑えられているようです。