きままにものづくり

日々の気付いたことなんかを書いてます。

SRM621Div1Medium

問題

ノード数Nの2つのツリーが与えられる。各ツリーはN-1のエッジを持っている。類似度S(e1, e2)を定義する。e1はツリー1、e2はツリー2のエッジを示す。ツリー1をe1で分断すると、ふたつのノードの集合ができる。ツリー2も同様である。このノードの集合を比較し、共通項の数の最大値を類似度とする。
e1とe2全ての組み合わせに対する類似度の総和を求めよ。

解法

愚直に実装すると、 O(N^4 log N)となる。e1とe2の組み合わせで O(N^2)、e1またはe2を選択したあとのノードの集合を計算するのに O(N)、集合同士の共通項を計算するのにO(N log N)かかる。
適切に前処理を行うことで、 O(N^2)となることを目指す。
e1を選ぶことでツリー1内のノードがどちらの集合に属しているかは判断することができる。これは、e2に依らず一定である。これにより O(N^3 log N)となるが、まだ不十分である。
次に共通項の計算を前処理を行うことで省略する。ツリー2の木構造はe1、e2によらず一定である。また、e1を決定することでツリー2内のノードがどちらの集合に属しているかも決定される。これにより、あるルートから出発した際のそれぞれの集合に属するノードの数も事前に計算することができる。

計算量

 O(N^2)

コード