O(n)

1.考虑统计前$i$点合法子串的个数 $f[i]$，这昂以s[i]结尾的合法序列个数为f[i]-f[p[i]]+1。

2.求 f[i]的过程可以用递推的思想，配合栈的数据结构。我们在深度优先遍历的过程中，如果当前结点为左括号，当前结点的编号进栈;如果为右括号且不空，则可以取出顶的编号，和当前结点配对。

3.递归结束前，恢复之前的栈结构(恢复现场)。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=500010;
vector<int> g[N];
int n;
int p[N];
char str[N];
LL f[N];
int stk[N],top;
void dfs(int u)
{
    if(str[u]=='(')
    {
        stk[++top]=u; //入栈
        f[u]=f[p[u]]; //一定不能选(等价于前面所有字符构成的合法序列方案)
        for(auto x:g[u]) //递归处理
        {
            dfs(x);
        }
        top--; //恢复现场
    }
    else
    {
        if(!top) //没有左括号(不匹配)
        {
            f[u]=f[p[u]];
            for(auto x:g[u])
            {
                dfs(x);
            }
        }
        else
        {
            int t=stk[top--]; //当前匹配的位置
            f[u]=f[p[u]]+f[p[t]]-f[p[p[t]]]+1; 
            //原来的加上p[t]结尾的合法序列的个数
            for(auto x:g[u])
            {
                dfs(x);
            }
            stk[++top]=t;
        }
    }
}
int main()
{
    cin>>n>>str+1;
    for(int i=2;i<=n;i++)
    {
        cin>>p[i];
        g[p[i]].push_back(i); //p[i]可以走到的点是i
    }
    dfs(1);
    LL res=0;
    for(int i=1;i<=n;i++) //根据题目描述求解
    {
        res=res^(i*f[i]);
    }
    cout<<res;
    return 0;
}