予め \(S\) を ( \(+ S + \) ) に置き換えておきます。この操作によって答えが変わらないことは簡単に確認できます。

ここで、\(S\) と子の順番を区別する根付き木の間に以下のように一対一対応を作ります。

\(S\) が正しい括弧列であることにより、対応する開き括弧と閉じ括弧の組を \(\frac{N}{2}\) 個作ることが出来る。この組が \(1\) 個の頂点に対応する。ここで、根となる頂点は \(S\) の左端の ( と右端の ) の組からなる頂点とする。 それ以外の頂点の親は、その括弧の組を含む括弧の組の中で、最も幅が小さいものとする。そして、ある頂点の子の順番は \(S\) での括弧の組の位置関係を保って配置する。(括弧列の性質により括弧の組が交差することはなく、親が同じ \(2\) 個の括弧の組同士の間では左右関係が定義出来る。)

根付き木からも両端の括弧が組となるような括弧列へ変換することが出来ます。(木 \(T\) の根の子を \(u_1,u_2,...,u_k\) としたとき、各 \(i\) に対して \(u_i\) を根とする部分木から得られる括弧列 \(t_i\) とすると、\(T\) と ( \(+ t_1 + t_2 + ... + t_k +\) ) が対応します。)

このとき、操作は以下のように言い換えられます。

• ある頂点 $v$ を選ぶ。$v$ の子が $u_1,u_2,...,u_k$ の順番で並んでいるとする。ここから連続する部分列を選びその部分列を反転する。そして、その部分列に含まれる頂点のいずれかを祖先に持つ頂点全てについて、その頂点の子の順番を反転する。(ここでの「反転」は問題文で定義されている「反転」とは異なり、列 $(a_1,a_2,\dots,a_n)$ を $(a_n,a_{n-1},...,a_1)$ に置き換える操作を指します。)

この操作を組み合わせることにより、以下の操作が実現できます。

• ある頂点 $v$ を選ぶ。$v$ の子が $u_1,u_2,...,u_k$ の順番で並んでいるとする。ここから連続する部分列を選び反転する。

また、新しいこの操作を用いても前の操作を行うことが出来るため、以降はこの操作を使い作ることの出来る木の個数を数え上げることにします。

この操作を用いることで、任意の頂点 \(v\) の子を好きな順番に並び替えることが出来ます。ですが、\(v\) の子を根とする部分木として同じものが存在する場合を考慮する必要があります。 つまり、問題は以下のように言い換えられます。

各頂点 \(v\) について、\(v\) を根とする部分木を \(t_v\) とする。\(t_1,t_2,\dots,t_n\) を、同型かどうかで区別するとき、これらの度数分布を求めよ。

ここで、根付き木 \(A,B\) が同型であるとは以下のいずれかを満たすことです。

• $A,B$ が共に頂点数 $1$ の木である。
• $A,B$ の子の個数が一致していて、それらを組にする方法であって「全ての組 $(a,b)$ について $a$ を根とする部分木と $b$ を根とする部分木が同型である」を満たすものが存在する。

これは部分木の頂点数の小さい方から判定することが可能です。具体的には、各部分木に整数のラベルを付けることを考えます。頂点数 \(1\) の木にはラベルとして \(1\) を付けます。ここで、木 \(T\) を根の子 \(u_1,u_2,\dots,u_k\) それぞれについてその頂点を根とする部分木につけられたラベルの多重集合と見ます。この多重集合が今までに現れていれば木 \(T\) のラベルはその多重集合となる木のラベルと等しくなります。今までに現れていなければ木 \(T\) のラベルはまだラベルとしてつけてない最小の正整数とします。

上記をそのまま実装するだけで \(\mathrm{O}(N \log N)\) でこの問題を解くことが出来ます。正整数でなく木を表す括弧列を正規化して持つ、\(N\) 個の部分木それぞれについて木の hash を愚直に求めるなどの \(\mathrm{O}(N^2)\) の解法でも許容されます。