構文解析する必要はない．まず + で切れるか試し，次に * で切れるか試し，次に ^ で切れるか試す．全部ダメなら，括弧で全体が覆われていればそれを外し，そうでなければ元の文字列そのままが答になる．
n 個目までの caravan に helm を計 h 個，armor を計 a 個積んでいるとき，同様にして積める boots の個数の最大値をDP．普通に概算すると 100*500*500*500*500 とかになるが実際は caravan の大きさ制限から枝を刈ると十分に速い．
問題文が曖昧な気がするが，とにかく時間優先で処理すればOK．特に各ジョブは1時間しか要さないので面倒なことはせずに，1時間ずつループを回して処理できるジョブを処理していくとよい．
- 1PE: 問題ごとに「テストケースとテストケースの答の間には空行を挟むこと」と「テストケースの答の後に空行を出力すること」があって紛らわしい……，いずれにせよちゃんと読む．
各ノードについてそれぞれのsignalが来た時，部分木がvalidになるかを計算する．全二分木で，与えられ方が優しいので簡単なループを回すだけで木DP可能．
書いてある通りに．
- 1WA: 隣接する辺が交差してると判定されないようにしていたら，辺どうしが重なるときにも交差してないと判定されていた．はじめから問題文に忠実に判定していればこのWAは無くせたはず．
