ABC252 G - Pre-Order 解説 - sankantsuのブログ

与えられたDFSの行きがけ順 $P_1,\ldots,P_N$ を達成するような $N$ 頂点の根付き木の数を求める問題．

部分木の形はその部分木の外にある頂点の置き方にはほとんど影響を与えないので，部分木ごとに数を数えて組み合わせる動的計画法が有力に見える．

そこで次のように定める．

$dp [ l ] [ r ]$ : 頂点 $P_l, \ldots, P_{r-1}$ からなる行きがけ順 $P_l, \ldots, P_{r-1}$ を満たす部分木の数

指定された行きがけ順を満たすために注意すべき点は，あるノードの子が複数ある場合には番号が小さいほうから訪れるという条件である．この条件より，ある頂点を兄弟ノードとして足す場合には，これから足す頂点の番号が現在ある兄弟ノードの中で最も番号が大きいものよりもさらに大きくなっている必要がある．

このことから，部分木の構成において根に対する直接の子ノードのうち最も頂点番号が大きいものがどれであるかで場合分けを行うという方針が見えてくる．そこで，下図のように頂点 $P_l, \ldots, P_{k-1}$ からなる部分木の根に $P_k, \ldots, P_r$ からなる部分木を接続することでより大きな部分木を構成することを考える．

部分木の構成

このとき与えられた行きがけ順を満たすためには，すでに $P_l$ の子になっている中でもっとも頂点番号が大きいもの ( $P_{k'}$ とする) よりも $P_k$ のほうが大きくなっていなければならない．したがって， $P_{k'}, \ldots, P_{k-1}$ からなる部分木を構成する段階で， $P_{k'} \lt P_{k}$ を満たすかどうかということを覚えておく必要がある．

そこで，次のようにもうひとつ配列を定める．

$dp' [ l ] [ r ]$ : 頂点 $P_l, \ldots, P_{r-1}$ からなる行きがけ順 $P_l, \ldots, P_{r-1}$ を満たす部分木のうち， $P_{k'} \lt P_r$ を満たすものの数

なお， $P_l$ が子を持たない (部分木が根のみからなる) 場合は行きがけ順の制約に関係なく任意の頂点を子としてつけ加えることができるので， $P_{k'} = -1$ と考えてよい．

以上の考察をもとに $dp, dp'$ が次のように計算できることがわかる．

部分木が根のみからなる場合は，

$\displaystyle dp [ l ] [ r ] = dp' [ l ] [ r ] = 1 \qquad (r - l = 1)$

$r - l > 1$ のときは，

$\displaystyle \hphantom{'}dp [ l ] [ r ] = \sum_{k \in \{ l+1, \ldots, r-1 \} } dp' [ l ] [ k ] \times dp [ k ] [ r ]$

$\displaystyle dp' [ l ] [ r ] = \sum_{ \scriptstyle k \in \{ l+1, \ldots, r-1 \} \atop \scriptstyle P_k \lt P_r } dp' [ l ] [ k ] \times dp [ k ] [ r ]$