AtCoder Regular Contest 103：E - Tr/ee
問題
解法
まず，s[0] は必ず 1 で s[|s| - 1] は必ず 0 でなければならない．なぜなら，葉に繋がる辺を切れば必ず大きさ 1 の部分木が出来て，どこかの辺で切ったら木全体が２つに分けられるため大きさ |s| の部分木は出来ないから．また，s[i] == s[|s| - 1 - i] でなければならない．なぜなら，大きさ k の部分木が出来る（出来ない）ということは，他方では大きさ |s| - k の部分木が出来る（出来ない）から．この３つの条件を満たしていれば木を構成することが出来る．
木を構成する過程で大きさ k の部分木が出来てほしくないとなった時，今まで作ってきた大きさ k - 1 の部分木の根に新しく頂点を付けてしまうと大きさ k の部分木が出来てしまう．そのため，新しく大きさ 1 の部分木を既存のものとは別に作り，大きさ m (m > k) の部分木が出来てほしいとなった時に，新しく追加する頂点といままでの部分木（大きさ k のもの 1 個と大きさ 1 のもの m - k 個）を辺で結べばよい．これは，s[i] == 1 を満たす i をメモしておけば O(|S|) で可能．
解答
