概要
基礎的な問題。
解法
集合 $S\subset {1,2,\ldots,n}$ に対して、頂点集合が $S$ と一致する二分木の個数を $\text{dp}[S]$ と書くことにします。これを適当なトポロジカル順序で計算していきます。
$S$ が空集合ならば、$\text{dp}[S] = 1$ です。そうでないとき、$S$ で二分木を作るときの根を $r$、左側の部分木の頂点集合を $L$、右側の部分木の頂点集合を $R$ として、以下のように計算できます。
- $S = {r}\amalg L \amalg R$ となる $r, L, R$ に対して、$|\sum_{v\in L}x_v – \sum_{v\in R}x_v| \in [a,b]$ であるとき、$\text{dp}[S]$ に $\text{dp}[L]\text{dp}[R]$ を加算する。
これを計算するにあたり、各 $S$ に対して、$L\amalg R = S\setminus{r}$ となる $(L,R)$ を列挙する必要があります。集合をビット列により整数にエンコードすれば、この操作は bit 演算により、$1$ 組の $(L,R)$ あたり $O(1)$ 時間で行えます。また、このような $(S,r,L,R)$ は全部で $O(N\cdot 3^N)$ 通りあります。よって、時間計算量 $O(N\cdot 3^N)$ で問題を解くことができます。
