AtCoder Grand Contest 047 D - Twin Binary Trees

お題箱より。

解法

ちょうど2本の特殊辺を持つ単純サイクルは、第1の木の異なる2つの葉の組み合わせと同じ個数だけ存在します。このサイクルは、その2つの葉の第1の木におけるLCAと、それらと接続されている第2の木の2つの葉のLCAとを2本のパスで結ぶものです。

f:id:betrue12:20201126233821p:plain

2つの葉の組み合わせを全て列挙していると間に合いません。そのため方針としては、第1の木の頂点を全探索し、その頂点を第1のLCAとするサイクルたちの積の総和をまとめて数えます。

第1の木の頂点 $v$ をLCAとするサイクルの積の総和は、具体的には以下の手順で求めることができます。

【手順1】まず $v$ から左側の子孫に進み、それぞれの葉から第2の木の根までのパスを全て辿る。このとき通過する第2の木の頂点 $i$ 全てに対して、 $v$ から頂点 $i$ までのパスにおける頂点番号の積を求めて配列の要素 $A_{i}$ に足しておく。

図において各頂点の左側に書いている赤い数字が該当します。

f:id:betrue12:20201126233954p:plain

【手順2】次に $v$ から右側の子孫に進み、それぞれの葉から第2の木の根までのパスを全て辿る。このとき通過する第2の木の頂点 $i$ 全てに対して、 $v$ から頂点 $i$ までのパスにおける頂点番号の積と、先ほど求めた $A_{i}$ との積を答えに足し合わせていく。

つまりこれは、 $v$ から左側に降りたパスと右側に降りたパスが合流する点において、別々に求めた頂点番号の積を掛け合わせて答えに足していることになります。掛けてちょうどサイクル1周分となるためには、手順2のほうでは頂点 $v$ とその頂点自身の値は含めずに積を計算すると良いです。図において各頂点の右側に書いている青い数字が該当します。

f:id:betrue12:20201126235319p:plain

ただしこの方法で数えると、サイクルは第2の木のほうのLCAだけでなく、さらにその祖先である頂点においても加算されてしまいます。しかも祖先においては第2のLCAからさらに余分に進んだ分の係数が掛けられた状態で加算されます。これを帳消しにするためには、第2の木を進むときに「親の頂点においては、これだけの値が余分に加算されてしまうはず」という値を伝播していって、答えから引けば良いです。

f:id:betrue12:20201126235200p:plain

【手順3】手順1において通過した第2の木の頂点を覚えておき、それらの頂点について $A_{i}$ の値を $0$ にリセットする。

これは次の $v$ に関する計算に移る前に必要です。 $A_{i}$ の値は手順1で通過した頂点だけしか変化していないため、それらの頂点だけについて処理することで計算量を抑えています。

これを全ての $v$ について試して合計すると答えを求められます。

計算量について考えます。全ての葉は、動作全体で $H-1$ 回だけ見られることになります。そして葉が1回見られるごとに、そのときの第1の木における頂点 $v$ へのパスを1回、第2の木の根へのパスを最大2回通ります。このパスの長さは $H$ 以下であり、葉の個数が $L$ 個であるため、全体計算量は $O(H^{2}L)$ となります。