読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

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

問題文

Problem - E - Codeforces

問題概要

  • 以下の条件を満たす木の総数を求めよ。
    • (u_i,v_i)\in E
    • LCA(a_i,b_i)=c_i

解法

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

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

部分木が3個あるのを考えるのは面倒なので、
f:id:pekempey:20151121165022p:plain:w350

まとめる。
f:id:pekempey:20151121165026p:plain:w350

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

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

それぞれ図で説明する。

  1. 左部分木のLCAが右部分木にあるのはおかしい。
    f:id:pekempey:20151121165103p:plain:w350

  2. 左部分木と右部分木のLCAは根でないとおかしい。
    f:id:pekempey:20151121165131p:plain:w350

  3. 左部分木と右部分木(根を含まない)の間に辺があるのはおかしい。
    f:id:pekempey:20151121165422p:plain:w350

  4. 左部分木と根の間に辺があるなら繋がないとまずい。
    f:id:pekempey:20151121165213p:plain:w350

  5. 左部分木と根の間に繋がないといけない辺が2つあるのはまずい。
    f:id:pekempey:20151121165240p:plain:w350

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

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

感想

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