n 頂点の木から辺を 1 つ取り除いてサイズ n の連結成分を作ることはできません」ので、Sn が 1 の場合も不可。他には、木において辺とは頂点集合を左右２つの連結成分に分けるものなので、Si と Sn-i が食い違う場合も不可。ここから答えの構築を考えた。大きさ１の連結成分から始めて１つずつ大きくして N/2 までの連結成分を作る。N/2 より大きい連結成分は大きさ N/2 以下の連結成分の片割れとして自動的にできあがっているので考えない。Si が 1 の場合、直線状に伸ばすことで大きさ i の連結成分が生じるようにする。Si = 0 の場合、葉を生やして横に大きくすることで大きさ i の連結成分が生じないようにする。最後に余った頂点をすべて葉としてくっつけて始末する。■提出 #31963209 (AC / 403 Byte / 131 ms)。以前に解こうとしたときは、大きさごとに連結成分を分けてプールして、小さい連結成分を組み合わせることでより大きい連結成分をプールするような処理を考えていた。実はプールする連結成分が１つだけでいいことと、大きさ１の連結成分(葉)がすごく便利に使えることに気がついたので今日は解けた。■コメントアウトしてある部分は、解答と入力に矛盾がないことを確かめるために、解答から入力と同形式の文字列を作って比較している。そのために judge.rb27 を書いた。■ブログを読んでいたら、解答のような木には「キャタピラ木 (Caterpillar tree)」という名前がついているらしい。わざわざ名前を付けて区別して嬉しい理由があるのでしょうね(調べない)。