HackerRank: Kingdom Division - read-eval-print loop

HackerRankの問題Kingdom Divisionの自分の解法が解説のものとは異なっていたのでアイデアをメモ。

木についての再帰を使って場合の数を数え上げる。そのために部分木に注目した際の２つのカテゴリを考える。

open: 部分木の根の都市が味方の都市と接していない。
closed: 部分木の根の都市が味方の都市と接している。

ただし、根以外のノードについては味方の都市と接しているものとする。以下では根の都市を一方の陣営に固定した場合を考える。葉にあたる都市についてopenな場合の数は1、closedな場合の数は0となる。また親ノードの場合の数は、子ノードの場合の数から次のように再帰的に計算できる。

openな場合の数

$\displaystyle Open(v) = \prod_{c \in child(v)}^{} Closed(c)$

closedな場合の数

$\displaystyle Closed(v) = \prod_{c \in child(v)}^{} (Open(c) + 2 \cdot Closed(c)) - \prod_{c \in child(v)}^{} Closed(c)$

説明しておくと、openな子は味方となるのが親しかいないのでopenな(=味方のいない)親の子になることはない。そのため $Open(v)$ は一番目の式で定まる。 $Closed(v)$ の計算で $Closed(c)$ を2倍しているのは敵味方どちらでもよいからである。またclosedな親には少なくとも一つ味方となるような子が必要なので、敵ばかりとなるような場合の数を引いている。

したがって、この問題はDFSを行うことで簡単に解くことができる。ただし再帰が深くなるので再帰関数で実装するとスタックオーバーフローを起こす（と思う）。