先考虑链。
考虑一个数珂以增加的贡献。
其实就是当前串后缀的合法个数。

但是暴力事 \(O(n\log n)\) 的。
括号串一定根栈脱不了干系。
考虑使用 DP。
怎么从前面的状态转移过来？
珂以发现：
前括号事没有贡献的。即为 \(0\)。
一个后括号，找到与之能匹配的前括号（珂以栈算出），这一段必然算一个。这个后括号的贡献事与之匹配的前括号的前一位的贡献 \(+1\)。
例：

为什么？圆圈最后一个数的贡献（即为与之匹配的前括号的前一位的贡献）即为其合法后缀数。
然后把这个后缀与我们的与之能匹配的前括号的这一段合法括号串拼起来，就成为了合法后缀。与之能匹配的前括号的这一段合法括号串也是一个合法后缀，所以要 \(+1\)。
有一个特殊情况。
我们找不到与之能匹配的前括号。所以这段贡献为 \(0\)。我们需要特判。否则使用 STL，会RE；手写的话，必须将 \(0\) 的贡献设为 \(-1\)。
如何做树？
每一个节点到根仍然是一条链。注意遍历完一个子树要把该子树的节点清除掉，也就是说，dfs 完之后，前括号要删掉；后括号要重新加上其搞掉的前括号。

P5658 [CSP-S2019] 括号树