A. Amusement Park
辺に向きをつけてできる DAG を数えるタイプの問題．
DAG は tosort 可能なのでトポロジカル順序を数える感じにします．
しかしトポロジカル順序は一意じゃないので一工夫必要です．
先頭の頂点を決めるのではなく，入次数 $0$ の頂点集合を決めるようにすれば自然に $O(3^n)$ の dp になります．
B. Magic Tree
葉側から順に，dp[その頂点の収穫日]=最大価値，という dp を求めていくことを考えます．
収穫日の候補は subtree 内のどれかに合わせたものだけ考えればよいです．
木 dp のマークテクによるマージでは，遅延セグメント木クエリのようなものが欲しくなるので，例えば DSU on Tree の要領で実装すると良いと思います．
C. Scissors and Tape
すごい問題ｗ
まあ有名問題です．分割合同，scissors-congruence などの検索語があります．（$3$ 次元の同じ体積の多面体だと変換可能とは言えないという，ヒルベルトの第 3 問題，デーンの定理も有名．）
逆操作が可能なので，何もかもを $1\time W$ の長方形にできることを示します．
三角形分割してそれぞれを長方形にすればよいです．
三角形をまず長方形にします．一番長い辺を底辺として図を書いて，中点から底辺に垂線をおろしてくる感じでできます．
長方形にしたら，高さが $[1/2,1]$ となるようにします．左右や上下に二分割して組み替えます．
高さが $[1/2,1]$ になったら，適当な方法で高さが $1$ の長方形にできます．
この過程を適切に実装すればよいです．
いくつかポイントを挙げておきます．
- 三角形分割は私は趣味実装したものを貼れました．多項式時間ならなんでもいいので引ける対角線を全探索で探して引くという感じの実装でもよいはず．
- 三角形の頂点順序の rotate は，scissors の $k=1$ でできる．
- 平行回転移動は tape の $k=1$ でできる．「移動して tape で貼り付ける」を 1 手で出来る設定ですが，私は混乱しそうだったので，移動と貼り付け操作を分けて実装しました．
- 計算誤差，操作回数とかは全然気にしなかったけど結果的に大丈夫でした．
- 注意点として，座標が $10^7$ 以下になるようにせよというものがあります．上では「高さが $1$」と説明しましたが，ダメです．高さが $10^6$ になるようにして実装しました．ここの実装のやりなおしで実装ミスを結構してしまいましたが，最初に縮小して出力時に拡大するのが簡単だった気がします（反省）．
