文字列 \(S\) に対し、\(S+T\) が全バーガーとなる \(T\) のうち長さが最小のものは存在し、「\(S\) 中に連続する同じ \(2\) 文字が存在する限り、その \(2\) 文字を削除する」という操作を可能な限り繰り返したときに、残った \(S\) を逆順にしたものが \(T\) になります。この \(T\) の長さを \(f(S)\) とおきます。

突然ですが、空文字列に相当するノードを用意し、Trie木っぽく木を作っていきます。ただし、Trie木とは異なるのは以下の点です。

• 各文字の情報は辺に持たせる
• 今いるノードから次の文字の辺がすでに貼られている場合は、ノードは新しく作らずにその辺をたどる

\(S[:i]\) まで見てこの木上をたどったときにいる頂点を \(X_i\) とすると、 \(f(S[i:j])=\begin{cases} 0 & (X[i]=X[j] \land X[i+1]=X[j-1]) \\ dist(X[i+1],X[j])+1 & (X[i] \neq X[j] \lor X[i+1] \neq X[j-1]) \end{cases}\)

\(X[i] \neq X[j] \lor X[i+1] \neq X[j-1]\) となる \((i,j)\) の個数は各辺を通る回数を考えるとわかるので、\(dist(X[i],X[j])=k\) となる \((i,j)\) の個数を \(k=0,1,\dots,K-1\) について求めることができればよいです。

小課題

\(dp[x][k]=\) 頂点 \(x\) の部分木内で \(x\) から距離 \(k\) の頂点の個数 を \(O(KN)\) で求めることができます。\(dist(X[i],X[j])=k\) となる \((i,j)\) の個数も各頂点 \(x\) の部分木内のものを足し合わせていくと、愚直に計算しても \(O(NK)\) で求めることができます（いわゆる2乗の木dpと同様の考え方です）。

満点

重心分解して再帰的に解きます。重心を \(g\) として、 \(X[i]\) から \(X[j]\) へのパスが \(g\) を通るようなものの個数を数えます。\(g\) で分解したそれぞれの木内で \(g\) からの距離が \(k\) の頂点の個数を求め、畳み込みを行うことで、\(dist(X[i],X[j])=k\) となる \((i,j)\) の個数を求めることができます。 計算量は全体で \(O(N(\log N)^2)\) になります。