2 つの操作列によって得られる \(a\) の列がどのような時に異なるのかを考えてみます。

まず、2 つの操作列において使う辺の集合が異なる場合を考えます。片方の操作列でのみ使用されている辺を \(e\) とします。入力で与えられる木 \(T\) から \(e\) を取り除いてできる 2 つの木を \(T_1, T_2\) とします。\(e\) を使わない操作列によって得られる \(a\) では、\(T_1\) に含まれる頂点の番号の集合と \(T_1\) に含まれる頂点に対応する \(a_n\) の集合が一致しますが、\(e\) を使う操作列では一致しません。よって、使う辺の集合が異なる場合は異なる列が得られることが分かります。

2 つの操作列において使う辺の集合が同じだとします。このとき実は次の 2 つの条件は等価です。

1. 2 つの操作列によって得られる列が一致する。
2. 全ての頂点 \(v\) について、使用する辺のうち \(v\) に隣接する辺の使われる相対順序が 2 つの操作列で一致している。

(証明) 以下では入力で与えられる木 \(T\) の全域部分グラフ \(G(V, E)\) を \(E\) が使用する辺集合であるグラフとして、単に「辺」と呼ぶときは \(G(V, E)\) に存在する辺を意味します。

(\(1. \to 2.\)) 対偶を取ります。2. が成り立たない時、頂点 \(v\) であって \(v\) に隣接する辺の使われる相対順序が 2 つの操作列で異なる頂点が存在します。\(v\) に隣接する辺を \(e_1, e_2, \dots, e_k\), \(e_i\) の \(v\) でない端点を \(u_i\) として、\(v\) を含む連結成分から \(v\) を取り除いた時に \(u_i\) を含む連結成分を \(C_i\) とします。
片方の操作列において \(e_1, e_2, \dots, e_k\) の順に \(v\) に隣接する辺が使われるとしても一般性を失いません。このとき、その操作列に従って操作をしたとき、\(v\) を介した駒のやり取りによって次のような状態になります。

• 駒 \(v\) は \(C_1\) に含まれる頂点の上にある
• \(C_1\) に含まれる頂点の番号に対応する駒は、 \(1\) 個だけ \(C_2\) 上にあり、それ以外は \(C_1\) 上にある
• \(C_2\) に含まれる頂点の番号に対応する駒は、 \(1\) 個だけ \(C_3\) 上にあり、それ以外は \(C_2\) 上にある
• \(\vdots\)
• \(C_{k-1}\) に含まれる頂点の番号に対応する駒は、 \(1\) 個だけ \(C_k\) 上にあり、それ以外は \(C_{k-1}\) 上にある
• \(C_k\) に含まれる頂点の番号に対応する駒は、 \(1\) 個だけ \(v\) 上にあり、それ以外は \(C_k\) 上にある

\(v\) に隣接する辺の使われる相対順序が異なる時に、上記のような \(v, C_1, C_2, \dots, C_k\) に関する相対的な関係性が一致しなくなることが確認できます。よって示されました。

(\(2. \to 1.\)) 辺の本数について帰納的に証明します。辺が \(0\) 本の時に命題が成り立つのは明らかです。辺が \(M\) 本の時に命題が成り立つとしたとき、\(M+1\) 本の時にどうなるかを考えます。
ここで、次の条件を満たす辺 \(e\) が少なくとも 1 本存在することが確認できます。

• \(e\) の両端点を \(u, v\) とする。\(u\) に隣接する辺の使われる相対順序で最後に来る辺と \(v\) に隣接する辺の使われる相対順序で最後に来る辺はともに \(e\) である。
  • (証明) \(G(V, E)\) において、隣接する辺が存在する頂点 \(w\) 全てについて、\(w\) に隣接する辺の使われる相対順序で最後に来る辺を赤く塗ることにする。すると、\(G(V, E)\) は森なので (次数 \(1\) 以上の頂点の個数) \(\gt\) (辺の本数) であるから 2 回以上塗られた辺が少なくとも 1 本存在することが鳩ノ巣原理により確認できる。(証明終わり)

今、\(2.\) の条件を満たす \(M+1\) 辺の操作列 \(S_1, S_2\) があるとします。ここから上の条件を満たす辺 \(e\) を 1 つ取り、\(S_1\) と \(S_2\) から \(e\) を取り除いた操作列 \(S'_1, S'_2\) を考えます。すると、\(S'_1\) と \(S'_2\) から得られる列が一致することは帰納法の過程から証明できます。また、\(e\) の両端点を \(u, v\) とした時、\(S_1\) から得られる列は \(S'_1\) から得られる列の \(a_u\) と \(a_v\) を swap した列です。よって、\(S_1\) と \(S_2\) から得られる列は一致します。

以上より命題は示されました。 (証明終わり)

また、各頂点 \(v\) について \(v\) に隣接する辺の使われる相対順序を自由に固定した時、それに対応する操作列が少なくとも 1 つ存在することが証明できます。

• (証明) 順序を 1 つ固定したときに「辺 \(e\) であって両端点における隣接する辺の使われる相対順序でともに最初に来る辺」が常に存在することが \(2. \to 1.\) の証明の時と同様に証明できる。よって、順序を 1 つ固定したときに、「両端点においてまだ使用されてない辺の中での相対順序で最初に来る辺」を使用するのを貪欲に繰り返すアルゴリズムによって操作列を 1 つ発見することが出来る。(証明終わり)

以上より、使用する辺を固定したときに、各頂点 \(v\) ごとの順序の割り当て方 \(\deg(v)!\) を掛け合わせたものが得られる列の個数と一致することがわかりました。よって、答えは全域部分グラフ全てについて \(\prod_{v \in V} \deg(v)!\) を足し合わせたものになります。これは DP によって \(\mathrm{O}(N^2)\) (あるいは畳み込みを利用した高速化により \(\mathrm{O}(N \log^2 N)\) ) で計算できます。