適当な根を選ぶことで、グラフは根付き木であるとします。

頂点に順列を割り当てることは、頂点に全順序を定めることと言い換えられます。問題の条件は、任意の頂点 \(v\) に対して次のどちらかが成り立つことと同値です（不等号は頂点に定める全順序に関するもの）：

• \(v\) と隣接する任意の\(w\) に対して \(v > w\)
• \(v\) と隣接する任意の\(w\) に対して \(v < w\)

前者が成り立つ \(v\) を「大きい点」、後者が成り立つ \(v\) を「小さい点」と呼ぶことにします。

---

◆ 木DP

\(v\) を根とする頂点数 \(n\) の部分根付き木に対して、次の値を \(\mathrm{dp}_v[i]\) と呼ぶことにします。

• 部分木 \(v\) の各頂点に全順序を定める方法であって、根 \(v\) が小さい点になるもののうち、根に割り当てられた値が小さい方から \(i\) 番目であるものの個数

これを葉から順に計算していく木DPにより、問題を解くことができます。木DPではまず、部分木の情報を併合して、部分森の情報を順に計算していくことになります。

\(n\) 頂点の森に対しては、各 \(i\) に対して

• 森の頂点に全順序を定める方法であって、すべての根が小さい点になるもののうち、根に割り当てられた値の最大値が小さい方から \(i\) 番目であるものの個数

を計算していきます。

---

◆ dp テーブルのマージ

次が計算できればよいことが分かります。

• 根と呼ばれる特別な頂点の定まっている \(n\) 元集合 \(A\)、\(m\) 元集合 \(B\) がある
• \(A\) 上の全順序であって、根が \(i\) 番目となるもののうち、何らかの条件を満たすものの個数 \(\mathrm{dp}_A[i]\) が与えられる。同様に \(\mathrm{dp}_B[j]\) も与えられる
• \(A\amalg B\) の全順序であって、\(A\), \(B\) への制限が条件を満たし、\(A,B\) の根のうち大きい方が \(i\) 番目であるようなものの個数 \(\mathrm{dp}[i]\) を計算せよ。

\(A, B\) の根のうちどちらが大きい方になるかによって、\(2\) 回計算することにします。

\(A\) の順序 \(a_1 < a_2 < \cdots < a_n\)、\(B\) の順序 \(b_1 < b_2 < \cdots < b_m\) を固定します。\(A\) の根が \(a_i\) であるとき、これが \(A\amalg B\) で \(i+j\) 番目の大きさとなるように順序を拡張する方法の個数は、以下の積として計算できます：

• \(a_1,\ldots,a_{i-1}\), \(b_1,\ldots,b_j\) の間の順序を定める：\(\binom{i-1+j}{i-1}\) 通り
• \(a_{i+1},\ldots,a_n\), \(b_{j+1},\ldots,b_m\) の間の順序を定める：\(\binom{n-i+m-j}{n-i}\) 通り

さらに \(a_i\) が \(B\) の根よりも大きくなるのは、\(B\) の根が \(b_1,\ldots,b_j\) のどれかのときです。したがって、\(\mathrm{dp}[i+j]\) には、\(\binom{i-1+j}{i-1}\binom{n-i+m-j}{n-i}\mathrm{dp}_A[i] (\mathrm{dp}_B[1]+\cdots+\mathrm{dp}_B[j])\) を加えることになります。累積和の事前計算のもと、これは全体で \(O(nm)\) 時間で行えます。

---

◆ 計算量解析

木DP において、大きさ \(n, m\) の部分森の情報が \(O(nm)\) 時間でマージできるとき、\(N\) 頂点からなる根付き木全体の情報は \(O(N^2)\) 時間で計算できます。この計算量解析の解説は例えば、

• ABC207 - F 解説 (https://atcoder.jp/contests/abc207/editorial/2155)

などを参照してください。 この計算量解析、あるいはそれが現れる木DPは、国内の競プロコミュニティではしばしば「2乗の木DP」と呼ばれます。