[CSP-S2019] 括号树
首先括号序列的合法性十分简单，在此不再赘述。考虑到对于一个点 \(u\)，我们如果求好了它的父节点的答案 \(ans_{p_u}\)，那么考虑如何求 \(ans_u\)。我们只需要求解以 \(u\) 为结尾的答案，发现如果 \(u\) 是左括号没关系，压入栈中。如果是右括号，贡献就是与它匹配的左括号的前一个右括号的贡献 \(+1\)，递归的时候注意回溯时恢复现场就可以了。
#include<cstdio>
#include<cstring>
using namespace std;
#define Ls(i,l,r) for(int i=l;i<r;++i)
#define Rs(i,l,r) for(int i=l;i>r;--i)
#define Le(i,l,r) for(int i=l;i<=r;++i)
#define Re(i,l,r) for(int i=l;i>=r;--i)
#define L(i,l) for(int i=0;i<l;++i)
#define E(i,l) for(int i=1;i<=l;++i)
#define W(t) while(t--)
typedef long long ll;
const int N=500010,M=2*N;
char c[N];
int n,h[N],e[M],ne[M],idx,g[N],st[N],top,p[N];
ll f[N];
void add(int a,int b){
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dfs(int u){
if(c[u]=='('){
f[u]=f[p[u]];
st[++top]=u;
for(int i=h[u];~i;i=ne[i])dfs(e[i]);
--top;
}
else{
if(!top){
f[u]=f[p[u]];
for(int i=h[u];~i;i=ne[i])dfs(e[i]);
}
else{
int t=st[top--];
g[u]=g[p[t]]+1;
f[u]=f[p[u]]+g[u];
for(int i=h[u];~i;i=ne[i])dfs(e[i]);
st[++top]=t;
}
}
}
int main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
// freopen("1.out","w",stdout);
// ios::sync_with_stdio(0);
// cin.tie(0);
// cout.tie(0);
#endif
// Insert Code Here
scanf("%d%s",&n,c+1);
memset(h,-1,n*4+4);
Le(i, 2, n){
scanf("%d",p+i);
add(p[i],i);
}
dfs(1);
ll ans=0;
E(i, n)ans^=f[i]*1ll*i;
printf("%lld",ans);
return 0;
}