問題概要
整数 $n$ と $n$ 頂点の木 $T$ が与えられる。
重心分解のような手続きを考える。これはつまり、 $1$ 段目では $T$ のどこかの頂点を選ぶ。その後選ばれた頂点が取り除かれるので、残った連結成分それぞれについて、 $2$ 段目ではどこかの頂点を選ぶ。それらが消えるので、… というのである。
この手続きとしてあり得る通り数を $\bmod 998244353$ で求めよ。ある $2$ つの手続き列は、ある $k$ があって $k$ 段目で取り除かれた頂点集合が異なる場合に、異なるとみなされる。
制約 : $1 \leq n \leq 5 \times 10^3$
解法
手続きの手順通りになぞっても指数通りの木が出てきて解けない。仕方ないので木 DP を考えると、意外とすんなり解ける。
- $\mathrm{dp}(u, k)$ : 頂点 $u$ の部分木を上の手順で分解する方法のうち、頂点 $u$ を $k$ 段目に取り除くものの個数
とすればうまくいく。$u$ が取り除かれてからは各部分木について独立に考えられて、逆にそれまでは全体として考えないといけないので、 $k$ の情報が必要になる。
これは二乗の木 DP の形の遷移になるので $O(n^2)$ で解ける。
雑記
見た目的には、これが解けるのはびっくりする。
コメント