本文共 1025 字，大约阅读时间需要 3 分钟。

solution:

本题是个树上问题，但我们不妨从线性状态上去考虑。这题就是一道区间dp了。

问题：给定字符串S，求有多少合法括号子串？

()()(())

设$f[i]$表示前$i$个的合法子串个数，$g[i]$表示以$i$结尾的合法字符串个数。

考虑如下转移：

$$g[i]=g[k]+1$$

$$f[i]=f[i-1]+g[i]$$

其中$[k+1,i]$为合法子串。

例如，上图中，$[5,8]$即$(())$为合法子串，所以$g[8]=g[4]+1=3$，$f[8]=f[7]+g[8]=3+3=6$

上述过程可以用栈模拟。时间复杂度是$O(n)$

如何扩展到树上呢？我们知道，$dfs$是有回溯操作的，即一个分支结束后可以回到原始状态。这就很巧妙了，我们只需要用一个栈模拟回溯操作就行了。这样就得到了点到根的原括号序列$S$。$O(1)$转移，时间复杂度$O(n)$。

#include
   
    #define int long longusing namespace std;const int N=5e5+5;char s[N];int n,fa[N],ans;int sta[N],Top,f[N],g[N];vector
    
      son[N];void dfs(int x) {   	if(s[x]=='(') {   		sta[++Top]=x;		f[x]=f[fa[x]];		g[x]=0;		for(int i=0;i
     
      0){   		int t=sta[Top--];		g[x]=g[fa[t]]+1;		f[x]=f[fa[x]]+g[x];		for(int i=0;i
     
    
   

转载地址：http://down.baihongyu.com/