はじめに

駒が置かれた木に対し、\(2\) 個以上の頂点を含む単純パスであって、端点のちょうど一方に駒が無く、他の頂点には駒が置かれているようなものを本解説では移動パスと呼ぶことにします。また、駒が置かれた木を \(1\) 本以上の移動パスに分解したものを移動パス分解と呼ぶことにします。
\(2\) つの移動パス分解はパス分解として異なる場合、および駒の配置が異なる場合に区別します。

条件を満たす配置の観察

ある条件を満たす駒の置き方を考えます。\(S_0,S_1\) を考えた時、\(1\) 回目の良い操作による駒の動きを求めるアルゴリズムは以下のようになります。

• すべての頂点を未処理とする。
• 未処理の頂点が無くなるまでの間、次のステップを繰り返す。
  • 未処理の頂点であって駒が置かれていないものを選び、\(v\) とする。
  • \(S_1\) に \(v\) が含まれないならば \(v\) を処理済みとする。
  • そうでない時、木から \(v\) を削除することで得られる \(1\) 個以上の連結成分のうち、その連結成分と \(S_1\) に共通して含まれる頂点数よりもこの時点で駒が置かれている頂点数が多い連結成分がただ \(1\) つ存在する。\(v\) に隣接する頂点のうちそのような連結成分に含まれるものの駒を \(v\) に移動させる。その後、\(v\) を処理済みとする。

\(S_0,S_1\) にともに含まれない頂点は存在しない(存在する場合、そのような頂点に駒を移動させる行為が想定出来るので条件を満たさない)ことを考えると、このアルゴリズムは条件を満たす配置から移動パス分解への対応を与えます。また、異なる配置は(対応するとしたら)異なる移動パス分解に対応することを考えると、条件を満たす配置は移動パス分解の集合 \(X\) のある部分集合 \(X'\) と一対一対応すると言えます。

\(X'\) に含まれる移動パス分解の条件

移動パス分解に対する駒の移動として、移動パスごとに駒を往復させる、というものが考えられます。もし駒の移動が一意でない場合はその移動パス分解は \(X'\) に含まれませんが、これは「ある隣接する移動パス \(x,y\) であって \(x\) の駒が \(y\) へ移り、かつ \(y\) の駒が他の移動パスに移らないようなものが存在する」というのと同値です。

証明
駒を他の移動パスに移すような移動が無い場合は駒の移動が一意なのでどこかの移動パスで他の移動パスに駒が移ります。
グラフが木であること、および各辺を通る駒が高々 \(1\) 個であることを考えると移動パス間で駒を移す関係性が循環せず、ゆえにその関係性の終点にあたる移動パスが存在します。その終点が \(y\) 、そこに駒を移してくる移動パスが \(x\) です。

以上のことを踏まえると、\(X'\) に含まれる移動パス分解は、任意の隣接する移動パス \(x,y\) が以下のいずれかに該当するものと言えます(場合分けで示せます)。

• 駒が置かれている端点と駒が置かれていない端点が辺で結ばれている。
• 端点でない頂点同士が辺で結ばれている。

\(|X'|\) を木dpで求める

木を適当な頂点を根とすることで根付き木とみなします。すると、各頂点を以下の \(5\) パターンに分類してDPをすることで条件を満たす移動パス分解の個数を求めることが出来ます。

1. その頂点またはその子孫に駒が置かれていない端点があるような移動パスに含まれる頂点であってもう一方の端点でないもの
   
2. その頂点またはその子孫に駒が置かれている端点があるような移動パスに含まれる頂点であってもう一方の端点でないもの
3. その頂点の子孫に駒が置かれていない端点があるような移動パスのもう一方の端点
4. その頂点の子孫に駒が置かれている端点があるような移動パスのもう一方の端点
5. その子孫に両端点があるような移動パスに含まれる頂点

参考までに遷移の例を一つだけ示します。

現在の頂点が \(1\) 番目のパターンとなるのは、\(X'\) の条件を考えると以下のどちらかを満たす場合です。

• 子がすべて \(3\) 番目のパターンである。
• ある子が \(1\) 番目のパターンかつ他の子が \(5\) 番目のパターンである。

よって、子のDPの値を元に条件を満たすのが何通りかを求めれば良いです。

また、対称性を考えると \(1\) 番目と \(2\) 番目のパターン, 及び \(3\) 番目と \(4\) 番目のパターンを同一視することも出来ます。この時、移動パス分解を端点で無い頂点同士を結ぶ辺で分けると独立に駒の置き方が \(2\) 通りとなるため, 端点でない頂点同士の遷移に際して \(2\) 倍すると良いです。