不难发现:

$sum[x]=sum[fa[x]]$+以$x$为结尾的合法数量

初想发现有点困难。

但貌似仔细想想之后，

$)$只能匹配一个$($

也就是说，一定在某个位置进行了累加(也就是"$AB$")

那么以$x$为结尾的合法数量可以视作为$1+$前面某一个位置为结尾的合法数量。

前面某一个位置为结尾的合法数量可以通过继承来获取。

维护继承可以用栈，因为只有栈顶的$($能用。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#define ull unsigned long long
#define ll long long
using namespace std;
const int N=5e5+5;
int sta[N],top,fa[N];ll sq[N],sum[N];
char s[N];
struct edge{int y,next;}a[N<<1];int len,last[N];
void ins(int x,int y){a[++len]=(edge){y,last[x]};last[x]=len;}
void dfs(int x)
{
    for(int k=last[x],y;k;k=a[k].next)
    {
        fa[y=a[k].y]=x;
        if(s[y]=='(')
        {
            sum[y]=sum[x];
            sta[++top]=y;
            dfs(y);
            --top;
        }
        else
        {
            if(top==0){sum[y]=sum[x];dfs(y);}
            else
            {
                int lst=sta[top--];
                sq[y]=sq[fa[lst]]+1;
                sum[y]=sum[x]+sq[y];
                dfs(y);
                sta[++top]=lst;
            }
        }
    }
}
int main()
{
    len=0;memset(last,0,sizeof(last));
    int n;scanf("%d",&n);
    scanf("%s",s+1);top=0;
    for(int i=2,y;i<=n;i++)scanf("%d",&y),ins(y,i);
    sum[1]=0;if(s[1]=='(')sta[++top]=1;dfs(1);
    ull ans=0;
    for(int i=1;i<=n;i++)
        ans^=i*sum[i];
    printf("%llu\n",ans);
    return 0;
}