A. Restricted Sorting
判定問題．
連結成分内で自由スワップ可能という形になります．
連結成分内でソートして全体がソートされているかをチェックします．
連結成分は，値が $x,y$ の間に辺が張れるなら $min,y$, $x,max$, $min,max$ のところに辺が張れるのでそれで．
結局非自明な連結成分はあるならば min, max を含むひとつだけです．
あとは二分探索しましたが，二分探索を外すのも容易です．
B. Shortest Statement Ever
$x,p$ の大小関係と $y,q$ の大小関係を固定して解くというのを $4$ 回やります．
あとは適当な桁 dp になります．
C. Jerry and Tom
結論として，最大の移動先に辺を張るというようにして有向木を作ってしまえばよいです．このように作った木を $T$ とすると，移動先はすべて親の subtree 内のどこかです．なので，subtree 内から脱出するには subtree の根を通らないといけないという形になっています．
なので Tom が $k$ 回移動するとき，常に親を選ぶとしてよいです．Jerry もそうだとしてよいこともわかります．
$\mathrm{LCA}(a,b)=v$ のとき，$f(a,b)$ は $a,b,v$ の深さを使って書けます．これである点を LCA とする場合の計算をまとめて行えばよいですが，これは DSU on Tree 的に実装しました．
D. Cool Problem
$c_i$ や $\sum c_i$ を $ax+by$ の形で保持して，組 $(c_i,\sum c_i)$ としてありうるものが何かを考えます．
考察だと結構難しい気がしますが，なんと実験すれば終わり．結局，$\sum c_i$ の $y$ の係数だけからすべてが決まるということになります．言い換えれば，$x=0,y=1$ とした場合にありうる $k$ を列挙できればよいです．
このとき $c_i$ は $0,1$ のどちらかで，ありうる $\sum c_i$ 全体は bitset 等で持てば $O(N^2/w)$ 計算量で解けます．
E. Doors and Keys
まだ．
F. Al Fine
F1, F2 ともにだいたい共通の考察ルートで．
入力について $b=[1,2,\ldots,n]$ としてよいです．実は先頭の $0$ はつけないままの方が簡単なのでそれで考えます．
方針として，$\mathrm{dp}[l][r]$ を，$l,\ldots,r$ を good な森にする方法に対する何かとします．何かとは：F1 ならば深さの最大値，F2 ならば数え上げです．
木の作り方としては，入力の列に対して $l,\ldots,r$ が左端が $l$ であるような区間になっていることが必要で，この必要条件のもと，$[l+1,r]$ を森にすればよいです．森の作り方としては，$[l,r]$ を木からなる連番に分割すればよいです．
順列があって，インデックスについても値についても区間であるものを考察．ということで，permutation tree を登場させます．$\mathrm{dp}[l][r]$ はこれのノードのところだけ計算すれば大丈夫，というのが結論です．
木が作れるような区間というのは限られていて，（長さ $1$ などの自明処理を除けば）
- 子 $[l_1,r_1], [l_2,r_2], \ldots, [l_k,r_k]$ が increasing であるようなノード内で
- $l_i=r_i$ であるような子があるときに，$[l_i,r_j]$ の形の木を作れる．
というようになります．
特に increasing でないノードは木を作れないし，森を作る方法も各子ノードごとに森を作るしかありません．なのでこういうところでの $\mathrm{dp}[l_1][r_k]$ は自明です．
子が increasing であるようなノードでについて考えます．
F1
$\mathrm{dp}[l_i][r_k]$ に相当するものを計算していくことができます．
先頭の木を子ノード内で作るときには，$\mathrm{dp}[l_i][r_i]$ と $\mathrm{dp}[l_{i+1}][r_k]$ の max です．
先頭の木をこのノード内で作るとき（$l_i=r_i$ が必要）には，$1+\mathrm{dp}[l_{i+1}][r_k]$ などとできます．
F2
$[l_i,r_i]$ を長さ $1$ であるか $2$ 以上であるかで分類します．$2$ 以上であるところについては結局子ノードで求めた $\mathrm{dp}[l_i][r_i]$ の積を共通の係数にできます．
帰着先はすべての $[l_i,r_i]$ が長さ $1, 2$ のどちらかであるような場合の計算です．
コンテスト中はここを区間 dp で $O(N^3)$ というものからなかなか抜け出せませんでした．初期の問題設定に戻ると分かりやすいです．結局，長さ $2$ の区間 $[a,a+1]$ があると，「$a,a+1$ は親が同じ葉です」というのが要請です．
- $1,2,\ldots,N$ を森にする（あるいは $0$ を根とする根付き木にする）．
- $1,2,\ldots,N$ が dfs 順のひとつ．
- $a,a+1$ は親が同じ葉ですという制約がいくつかある．
という状態になります．最後の条件がなかったら，数え上げはカタラン数です．dfs するときの深さの変化を考えればカッコ列登場です．
「$a,a+1$ は親が同じ葉です」については，カッコ列でいえば，$a,a+1$ 回目の開きかっこは続けて即閉じられるという条件です（”()()”）．
例の累積和を状態とする dp で，これは $O(N^2)$ 時間になります．
permutation tree のノードでこれをやりますが，計算量は $N$ 頂点の木の次数の $2$ 乗和でという形で $O(N^2)$ でおさえられています．
G. Many Cartesian Trees
まだ
