条件から木の辺に関するものを除いたものを Chain Graph Pair(略して CGP) と呼ぶことにする。 CGP に関して、以下の性質が成り立つ。

[性質] CGP \((G, H)\) の辺を合わせたグラフ \(G'\) において、\(G'\) はトポロジカルソート可能。

---

[証明] 有向サイクルがないことを示す。Chain Graph は \(a \rightarrow b\) が到達可能なら、\(a \rightarrow b\) の辺が存在することが性質からわかる。 有向サイクルがあったとして矛盾を導く。有向サイクルの中で含まれる辺の数が最小のものを取る。 明らかに辺の数が二つのサイクルは存在しないので、この長さは 3 以上である。 また、\(G\) 由来の辺が二つ連続した場合、これらを直接結ぶ辺が存在するはずなので最小性に矛盾する。よって、サイクルの辺は元々属するグラフが順に \(G, H, G, H, \ldots\) となっている。

サイクル内の連続する 3 点 \(A, B, C\) を取る。一般性を失わず、\((A, B) \in G\) としてよい。 今、\((B, C) \in H\) である。 サイクルの最小性から、\((A, C)\) は \(C \rightarrow A\) の向きで \(G, H\) のいずれかに含まれている。

\(G\) に含まれるとき

\((C, A), (A, B) \in G\) より、\((C, B) \in G\) のはずなので矛盾。

\(H\) に含まれるとき

\((B, C), (C, A) \in H\) より、\((B, A) \in H\) のはずなので矛盾。

よって、\(G'\) はトポロジカルソート可能である。[証明終]

---

[性質] 頂点数 \(N\) の CGP は二つの順列の組 \((P, Q)\) との間に一対一対応がある。

---

[順列の組から CGP の構成] \(1 \le i < j \le N\) に対して、\(Q_i < Q_j\) なら \(G\) に、\(Q_i > Q_j\) なら \(H\) に \(P_i\) から \(P_j\) の向きに辺を貼る。

[CGP から順列の組の生成] 合算したグラフ \(G'\) をトポロジカルソートする。これは一意に定まる。 頂点をトポロジカルソートした順列を \(P\) とする。

\(V = \{ 1, \ldots, N\}\) とする。
\(i = 1, \ldots, N\) の順に 頂点 \(P_i\) の出次数を \(k\) として、\(V\) の中で大きい方から \(K+1\) 番目の値を \(Q_i\) とする。

これらが互いに逆になっていることは簡単に確認できる。

---

この対応を利用して、CGP を数える代わりに対応する順列の組の数を数える。

順列 \(T\) の逆置換を \(T^{-1}\) と書く。 \(x\) から \(y\) に向かう辺があることは、\(P^{-1}_x < P^{-1}_y\) と、\(Q_{P^{-1}_x} < Q_{P^{-1}_y}\) がともに成り立つことと同値である。

木の辺の向きが定まっているとする。上の条件を \(P, Q\) それぞれ書き入れよう。すると、頂点の番号は違うが、同じ形の有向グラフになる。 結局、\((P, Q)\) の組の数はトポロジカルソートソートされた順列の組の数に等しい。

木の辺の向きの定め方と上記の組の組を数える方法を考える。

これは順列の組に対して、それぞれが今既にみた頂点の中で何番目に対応しているかを管理する木 DP で解くことができる。そのまま実装すると \(O(N^6)\) となるが、2 次元の imos 法を用いることで \(O(N^4)\) に改善することが出来る。