公式の解説に具体例とかの図がなくて辛い人がいるかもしれないのと、自分が本番のときに紙面で木を作りまくって考察した痕跡を残すための記事です。
条件を満たす配置とは
例えば以下の木に置かれたコマの配置は条件を満たします。この記事では黒マスをコマとして表現しています。
このコマの配置は1回操作をするたびに下の配置と行ったり来たりします。
この図のコマは左の3つのコマは左の4つの頂点を移動していて、右の2つのコマは右の3つの頂点を移動しています。なので、この木を２つのパス分解します。
具体的には以下のように分解します。
このパスは端点の一方にコマが置かれていないマスがあり、1回操作をするたびにその頂点が入れ替わります。 (コマが置かれていない頂点が端点でないとき、移動がそのパス内では不可能になるため)
もう1つ例を挙げます。以下のコマの配置も条件を満たします。
パスは以下のように分解されます。
このパス分解することが最終的に数え上げるときのベースになるのですが、パス分解ができるからといって条件を満たすわけではありません。
条件を満たすパス分解とは？
以下の配置を見てみましょう
この配置もさっきみたいにパス分解できそうです。
しかし、この配置は良い配置ではありません。 なぜなら以下のように移動できるからです。
なぜうまくいっていないかというと、辺で隣り合っている端点のどちらもにコマが置いてある状態だと、本来移動できないはずの方向へ移動することができるからです。(下の図では真ん中の頂点が右に移動できてしまっています)
このような考察から、辺で隣り合っている別のパスの端点同士はどちらか一方のみに必ずコマが置いてある状態でなければなりません。
また、以下の置き方も良い置き方ではありません。
この実験からパスの端点でない頂点と別のパスの端点が辺で隣り合ってはいけないことがわかります。
以上のことを踏まえると辺でとなり合う異なる２つのパスは以下のいずれかが成り立っていないといけません。
- コマが置かれている端点とコマが置かれていない端点が辺で結ばれている。
- 端点でない頂点同士が辺で結ばれている。
パスに対するコマの置き方の数は？
パスを決めたとき、そのパスに沿った良いコマの配置は何通りあるのでしょうか。 以下のパスを参考にします。
パスが4つあるので $2^4$ 通り置けるのかというとそうではありません。 例えば以下の配置は条件を満たしません。
これはなぜかというと、コマの置かれていな端点同士が結ばれているからです。
端点同士が結ばれている時はこのようにコマの置き方に制約が生じます。
一方、端点でない頂点同士が結ばれている時はそれらの間に制約が生じません。
以上の考察より、端点でない頂点同士が結ばれているパスでない辺の数を $a$ とおくと、コマの置き方は $2^{a+1}$ 通りあります。(この例だと a=1 なので 4通り)
木dp
ここまで考察できたら木dpでパスの置き方とその置き方に対するコマの数を数え上げます。
木の頂点の状態は以下の4つに場合分けします。
状態0 端点で、もう一方の端点はその頂点の子孫にある。
状態1 端点で、もう一方の端点はその頂点の子孫にない。
状態2 端点でない頂点で、端点のうち一方はその頂点の子孫の頂点で、もう一方は子孫でない頂点。
状態3 端点でない頂点で、そのパスの端点はどちらともその頂点の子孫である。
それぞれの状態の直属の子供は以下の条件を満たしている必要があります。
状態0
子供のうち、1つが状態1もしくは2で、その他の子供は0
状態1
全ての子供が0、もしくは、子供が存在しない。
状態2
子供のうち、1つが状態1もしくは2で、その他の子供は3
状態3
子供のうち、状態1もしくは2なものがちょうど2つ
状態3のときに、「パスに対するコマの置き方」のパートでの考察にあった通り、状態数を2倍します。
根の頂点が状態0だった時も2倍します。
あとはこれを実装するだけです。
終わりに
ここまで読んでくれてありがとうございます。 思ったより長くなってしまいました。
この問題はAtCoder Problem上では新ARCのDの中で最難関のdiff2900↑でした。
しかし、個人的にはこの問題は天才パートもないし、難しい知識も必要ないし(木dp程度)、考察を丁寧にすれば実装もそんなに苦しくない問題です。
なのでdiffの割には取りやすい問題だと思っています。(多くの人が解けなくてこのdiffになっているのでそんなわけないだろ!という意見があって当然です)
頑張ってコンテスト中に解けるように精進頑張ろう!
