括号树

其实就是把括号匹配拿到了树上（外加一个简单的DP）
注意回退就ok了

#include<bits/stdc++.h>
using namespace std;
struct oppo{
    long long to,next;
}rood[500005];
long long head[500005],tot;
void add(long long from,long long to)
{
    rood[++tot].to=to;
    rood[tot].next=head[from];
    head[from]=tot;
}
char a[500005];
long long n,t;
struct vivo{
    char a;
    long long x;
}st;
stack< vivo > v;
long long dp[500005];
long long ans[500005];
void dfs(long long x,long long fa,long long deep)
{
    long long flag=0;
    if(a[x]=='(')
    {
        dp[deep]=0;
        st.a='(';
        st.x=deep;
        v.push(st);
    }
    else if(a[x]==')')
    {
        if(v.size()&&v.top().a=='(')
        {
            dp[deep]=dp[v.top().x-1]+1;
            flag=v.top().x;
            v.pop();
        }
        else
        {
            st.a=')';
            st.x=deep;
            v.push(st);
            dp[deep]=0;
        }
    }
    if(fa!=-1)
        ans[x]=ans[fa]+dp[deep];
    for(long long i=head[x];i;i=rood[i].next)
    {
        dfs(rood[i].to,x,deep+1);
    }
    //还原 
    if(a[x]=='(')
    {
        v.pop();
    }
    else if(a[x]==')')
    {
        if(flag)
        {
            st.x=flag;
            st.a='(';
            v.push(st);
        }
        else
            v.pop();
    }
}
int main()
{
    cin>>n;
    for(long long i=1;i<=n;i++)
        scanf(" %c",&a[i]);
    for(long long i=2;i<=n;i++)
    {
        scanf("%lld",&t);
        add(t,i);
    }
    dfs(1,-1,1);
    long long all=0;
    for(long long i=1;i<=n;i++)
        all=all^(i*ans[i]);
    cout<<all<<endl;
    return 0;
}