题解

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=5e5+10;
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<<3)+(x<<1)+(ch^48);ch=getchar();}
return xf;
}
int n,d[N],fa[N],a[N],b[N],k[N],ans;
signed main(){
n=read();
for(int i=1;i<=n;i++){
char ch=getchar();
while(ch!='('&&ch!=')') ch=getchar();
if(ch=='(') d[i]=1;
else d[i]=-1;
}
for(int i=2;i<=n;i++)
fa[i]=read();
for(int i=1;i<=n;i++){
if(i==1) continue;
if(d[i]==1) k[i]=k[fa[i]];
else{
int now=fa[i];
while(d[now]!=1&&now)
now=fa[b[now]];
if(now){
a[i]=a[fa[now]]+1;
b[i]=now;
}
k[i]=k[fa[i]]+a[i];
}
ans=ans^(ik[i]);
}
cout<<ans<<endl;
return 0;
}