第一，找到了从当前位置往根节点方向走第一个没有匹配的左括号，这样从这个左括号到当前位置一定是合法的子串，因为这两个括号之间所有的左括号一定匹配了一个子串上的右括号。
第二，第一个没有匹配的左括号前面紧挨着它的合法子串可以和第一种情况的子串共同构成新的合法子串，而紧挨着当前链上第一个没有匹配的左括号的位置一定是固定的。
上面两种情况加起来得到了这个有括号的总计答案。
考虑设计\(dp\)转移状态。从第二部分入手，我们发现因为用来转移的位置是固定的（它紧挨着当前链上第一个没有匹配的左括号），当前加入点的位置也是固定的，考虑将前者作为后者的子问题。所以我们得到，用\(dp[i]\)表示从根节点走到点\(i\)的链上严格以\(i\)结尾的合法子串数目。
同时我们需要维护“第一个没有匹配的左括号的位置”，所以可以借助暴力的思路使用一个栈。用栈顶表示当前链上第一个没有匹配的左括号的位置，每次遇到一个左括号进栈并标记\(dp[i]=0\)，遇到一个右括号时如果栈为空则标记\(dp[i]=0\)因为没有可以和它匹配的左括号；否则弹出栈顶，标记\(dp[i]=dp[fa[s[top]]]+1\)。那个加上的\(1\)表示这个加入的右括号和第一个没有匹配的左括号匹配上的子串，这个没有匹配的左括号是\(s[top]\)；所以\(fa[s[top]]\)表示紧挨着它的第一个括号，即\(dp[fa[s[top]]]\)表示这个位置对应上述第二种情况。因为从这个点走到根节点且以这个点结尾的合法子串数目恰好每个合法子串都可以和上面那个加上的\(1\)组成一个新的子串。
比如说，从()(变成()()，新加入的右括号在对应那个没有匹配的左括号同时，这个括号对又能和前面匹配好的()组成新的合法串()()。
注意一个问题。因为我们全局只使用一个栈，所以我们当搜完一棵子树并回溯的时候必须恢复栈的状态到刚搜到这个点时的状态。所以我们考虑递归地恢复状态。对于每次搜索我们只有进栈/出栈两种可能，所以如果\(dp\)这个点进过栈，我们就将其弹出；如果出过栈我们就重新进栈。
代码。
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<cctype> #include<algorithm> #include<stack> #define int long long #define rep(i,a,n) for(register int i=a;i<=n;++i) #define dwn(i,n,a) for(register int i=n;i>=a;--i) using namespace std; int n,head[500050],num,f[500050],dp[500050],ans; stack<int> s; char str[500050]; struct edge { int u,v,nxt; }e[1000050]; inline int read() { int x=0,f=1; char ch=getchar(); while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();} while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} return x*f; } void write(int x) { if(x<0)putchar('-'),x=-x; if(x==0)return; write(x/10); putchar('0'+x%10); } void add(int u,int v) { e[++num].u=u;e[num].v=v; e[num].nxt=head[u];head[u]=num; } void DP(int x,int fa,int cost) { int flag=0; if(str[x]=='(')s.push(x); else { if(s.empty())dp[x]=0; else { flag=s.top();//如果有过出栈操作就再进去 s.pop(); dp[x]=dp[f[flag]]+1; } } for(register int st=head[x];~st;st=e[st].nxt) { int y=e[st].v; if(y==fa)continue; DP(y,x,cost+dp[x]); } if(flag)s.push(flag);//恢复 ans^=x*(cost+dp[x]);//cost记录不算这个点的答案 if(str[x]=='(')s.pop();//只有这个点是'('才进过栈 return; } signed main() { memset(head,-1,sizeof head); n=read(); cin>>(str+1); rep(i,2,n) { f[i]=read(); add(i,f[i]); add(f[i],i); } DP(1,-1,0); if(ans)write(ans); else putchar('0'); return 0; } /* 7 (()))(( 1 2 1 2 5 3 */