Problem
Solution
Thinking 1
对于某一个子树，它自身情况数为左子树情况数*右子树情况数。
Thinking 2
设\(dp[i,j]\)为\(S[i,j]\)能构成的情况数。
不难发现，如果它是一个合法的子树，那么要满足：
- \(j - i + 1\)为奇数
- \(S_i = S_j\)
Thinking 3
不难发现，对于一个树，它的dfs序为:
Rt | L | Rt | R
枚举断点\(k\)，左子树为\(S[i + 1,k - 1]\)，右子树为\(S[k,j]\)。
\[dp[i,j] = \sum_{i + 2 \le k \le j,S_i = S_k = S_j} dp[i + 1,k - 1] \cdot dp[k,j]
\]
彳亍，完成了。