素朴な解法として、

• \(\mathrm{dp}(a, b, k) \coloneqq\) 行きがけ順 \(a, a+1, \dots, a+k-1\) の頂点の通りがけ順の集合が \(b, b+1, \dots, b+k-1\) であるときの、これらの頂点のみからなる部分木としてありうるものの個数

という動的計画法を考えると、状態 \(O(N^3)\) 個、遷移 \(O(N)\) 時間で全体 \(O(N^4)\) 時間となりますが、この方法では実行時間制限に間に合わせることは難しいです。

以下では異なるアプローチにより、時間計算量を \(O(N^3)\) に改善します。

1. 全単射の利用

二分木、順序木（子に順序がついた木。英語で ordinal tree）、括弧列、経路数はいずれもカタラン数で数えられる対象であり、実際に全単射を持ちます。全単射を利用して最終的に問題を経路数の問題に言い換え、見通しをよくします。また、その後の解法を考える際にもこの全単射を再び利用することがあります。

1-1. 二分木から順序木へ

\(n\) 頂点の二分木と \(n+1\) 頂点の順序木の間には、次のような全単射があります（cf. 二重連鎖木）。

• 二分木は、順序木のうちの根でない頂点を持つ。
• 順序木において頂点 \(v\) の子が順に \(c_1, \dots, c_k\) であるとき、二分木における親子関係は次のようにする。
  • （\(v\) が根でないとき、）\(v\) の左の子を \(c_1\) とする。
  • \(c_1\) の右の子を \(c_2\) とする。
  • \(c_2\) の右の子を \(c_3\) とする。
  • \(\vdots\)
  • \(c_{k-1}\) の右の子を \(c_k\) とする。

このとき、二分木において行きがけ順 \(a\)、通りがけ順 \(b\) の頂点は、順序木において行きがけ順 \(a\)、帰りがけ順 \(b\) となります（ただし、順序木で行きがけ順・帰りがけ順を考えるとき、根は含めないものとします）。

1-2. 順序木から括弧列へ

\(n+1\) 頂点の順序木に対して深さ優先探索を行った際、子に潜るたびに ( を、親に戻るたびに ) を追加して得られる長さ \(2n\) の正しい括弧列を考えます。

括弧列において ( のうち左から \(a\) 番目である文字は、順序木において行きがけ順 \(a\) の頂点に潜ったことを意味し、括弧列において ) のうち左から \(b\) 番目である文字は、順序木において帰りがけ順 \(b\) の頂点からその親に戻ったことを意味します。順序木において行きがけ順 \(a\) の頂点の帰りがけ順が \(b\) であるとき、括弧列におけるこの \(2\) つの文字は対応する括弧となります。

よって、問題は次のように言い換えられます。

長さ \(2N\) の正しい括弧列であって、\(i=1, \dots, M\) に対し、( のうち左から \(A_i\) 番目のものと、) のうち左から \(B_i\) 番目のものが対応するようなものの個数を求めよ。

1-3. 括弧列から経路数へ

長さ \(2n\) の正しい括弧列は、( を右に移動する操作、) を上に移動する操作に対応させたとき、座標平面上で \((0, 0)\) から \((n, n)\) まで領域 \(y \leq x\) の外に出ないように移動する方法に対応します。

以上より、問題は次のように言い換えられます。

次の条件を満たす、正整数 \(d_1, \dots, d_M\) と、\((0, 0)\) から \((N+1, N+1)\) まで右または上への移動で行く方法の組の個数を求めよ。ただし、\((A_0, B_0) = (0, N+1), d_0 = N + 1\) とする。

• 条件： 各 \(i = 0, \dots, M\) に対し、経路は \((A_i, B_i - d_i)\) および \((A_i + d_i, B_i)\) を通り、かつ \((A_i, B_i - d_i)\) と \((A_i + d_i, B_i)\) を結ぶ線分のうち端点以外は通らない。

2. 木 DP

\(M+1\) 頂点の順序木であって、\(A, B\) をそれぞれ座標圧縮した列を \(A', B'\) としたとき、行きがけ順 \(A'_i\) の頂点の帰りがけ順が \(B'_i\) となっているようなものを考えます（存在しなければ答えは \(0\) です）。

この順序木において、頂点 \(v\) の子が順に \(c_1, \dots, c_k\) であるとします。すると、経路上で \((A_v, B_v - d_v)\) から \((A_v + d_v, B_v)\) まで移動する際に、\((A_v, B_v - d_v),\) \((A_{c_1}, B_{c_1} - d_{c_1}),\) \((A_{c_1} + d_{c_1}, B_{c_1}),\) \(\dots,\) \((A_{c_k}, B_{c_k} - d_{c_k}),\) \((A_{c_k} + d_{c_k}, B_{c_k}),\) \((A_v + d_v, B_v)\) を順に経由することになります。

これに基づき、順序木の上で木 DP を行います。

• \(f(v, d) \coloneqq d_v\) を \(d\) にし、\((A_v, B_v - d)\) から \((A_v + d, B_v)\) まで条件を満たして移動する方法の個数

とします。答えは \(f(0, N+1)\) です。

木 DP の遷移の際は、さらに内部で DP を行います。

• \(g_{v,d}(i, e) \coloneqq\) \(d_{c_1}, \dots, d_{c_i}\) の値を決め、特に \(d_{c_i} = e\) にすることを決めて、\((A_v, B_v - d)\) から \((A_{c_i} + e, B_{c_i})\) まで条件を満たして移動する方法の個数

遷移の際の係数として、「直線 \(y = x\) を一度も通らずに \((s_x, s_y)\) から \((t_x, t_y)\) まで右または上への移動で行く方法の個数」のような値が必要になりますが、この値は鏡像法を用いて導出できます。

3. 計算量の改善とその解析

上記の木 DP では、\(g_{v,d}(i-1, e)\) から \(g_{v,d}(i, e')\) に遷移する際、\(v, d, i, e, e'\) を変数とする \(5\) 重ループが回ることになり、この部分が時間計算量のボトルネックになります。\((v, i)\) の個数は \(O(M)\) で、\(d, e, e'\) がそれぞれ \(O(N)\) 個あるという評価に基づくと、時間計算量は \(O(MN^3)\) と評価できます。

ここで実は、次の工夫を行うと時間計算量が改善されます。

• \(e \leq A_{c_i} - A_{c_{i-1}}, e' \leq B_{c_i} - B_{c_{i-1}}\) としてよいので、\(e, e'\) のループではこの範囲のみを回すようにする。

すべての隣接兄弟 \(c, c'\) についての \((A_{c'} - A_c) \cdot (B_{c'} - B_c)\) の和が \(O(N^2)\) であることを示します。先述した全単射で順序木を二分木に変換することを考えます。すると、この二分木は、\(B'\) を添字、\(A'\) を値と思った列の min 基準の cartesian tree になっています。順序木での隣接兄弟 \(c, c'\) は、二分木では親と右の子の関係になっています。グリッド上に \((A_c, B_c), (A_{c'}, B_{c'})\) を端点とする軸に平行な長方形をすべて描くことを考えると、cartesian tree の性質より、これらの長方形は端点以外で重ならないことがわかります。よって長方形の面積の総和はグリッドの面積 \(N^2\) 程度で抑えられ、主張が従います。

したがって、上記の \(5\) 重ループの \((v, i, e, e')\) の個数が \(O(N^2)\) と評価でき、\(d\) の個数は \(O(N)\) なので、時間計算量は \(O(N^3)\) となります。