Typical DP Contest N - 木
問題
頂点の木を書く。
木を書いている途中で、すでに書いている全ての辺が連結になるような書き方の数を求める。
考察
根付き木の根からの生やし方の数を考える。
根付き木のノード数が1のとき1通り。
根の個の子を根とする部分木のノードの数が
、生やし方の数をそれぞれ
とする。
この根付き木の生やし方の数は
である。これはDFSで求めることができる。
全ての辺に対して、その辺を根とみなすと全てのバターンを計算できる。
頂点の木を書く。
木を書いている途中で、すでに書いている全ての辺が連結になるような書き方の数を求める。
根付き木の根からの生やし方の数を考える。
根付き木のノード数が1のとき1通り。
根の個の子を根とする部分木のノードの数が
、生やし方の数をそれぞれ
とする。
この根付き木の生やし方の数は
である。これはDFSで求めることができる。
全ての辺に対して、その辺を根とみなすと全てのバターンを計算できる。