https://packer-jp.hatenadiary.jp/entry/2018/10/07/201547

木が構築可能であるための、次の必要条件が浮かびます。

実はこれらは十分条件でもあります。具体的には、次のようにして構成できます。

頂点 $1, 2$ 間を繋ぐ。
直前に頂点 $t, i(t < i)$ 間を繋いでいたとする。 $s_{i}=1$ の場合、頂点 $i, i+1$ 間を繋ぐ。 $s_{i}=0$ の場合、頂点 $t, i+1$ 間を繋ぐ。

このようにすれば、 $s_{i}=1$ のとき、頂点 $i, i+1$ 間の辺を切ればサイズ $i, n-i$ の連結成分ができます。 $s_{i}=0$ のとき、頂点 $t, i+1$ 間の辺を切ってもサイズ $1, n-1$ の連結成分しかできません。

構築は色々なパターンがあって一般論を見出すのが難しいですが、とりあえず手を動かしてみるのがいいような気がします。