Codeforces Round #332 (Div. 2) E. Sandy and Nuts

問題文

Problem - E - Codeforces

問題概要

• 以下の条件を満たす木の総数を求めよ。
  • 
  • 

解法

f(s,root):=（頂点集合がs、根がroot、かつ条件を満たす木の総数 ）
としてメモ化再帰をすれば解ける。

例としてf=(0,{0,1,2,3,4,5,6,7})の場合を考える。 まず頂点集合を幾つかの部分木に分割する。このとき左部分木にはかならず1を含めるようにする（ダブルカウント回避）。

部分木が3個あるのを考えるのは面倒なので、

まとめる。

次の5つを意識しながら計算を行う。

1. 左部分木のLCAが右部分木にあるのはおかしい。
2. 左部分木と右部分木のLCAは根でないとおかしい。
3. 左部分木と右部分木（根を含まない）の間に辺があるのはおかしい。
4. 左部分木と根の間に辺があるなら繋がないとまずい。
5. 左部分木と根の間に繋がないといけない辺が2つあるのはまずい。

それぞれ図で説明する。

1. 左部分木のLCAが右部分木にあるのはおかしい。
   

2. 左部分木と右部分木のLCAは根でないとおかしい。
   

3. 左部分木と右部分木（根を含まない）の間に辺があるのはおかしい。
   

4. 左部分木と根の間に辺があるなら繋がないとまずい。
   

5. 左部分木と根の間に繋がないといけない辺が2つあるのはまずい。
   

LCA(i,i)=jや、LCA(i,j)が2通り以上ある入力に注意。

Codeforces Round #332 (Div. 2) E. Sandy and Nuts

感想

CODE FESTIVAL決勝Gのスタンプラリーで使った3つ以上の部分木をまとめるテクが役に立った。