Miku

so crazy

因为把stack的类型写成bool 把自己搞自闭了

思路，显然如果一个点是（，那么不会有贡献，只要压入队列，答案继承父亲就行了

如果是），如果能匹配，就判断（的父亲是什么，如果是），那么显然把根节点到)的父亲的序列中与刚匹配的（）相接的部分加上刚匹配的（）也是合法的

不考虑刚匹配的（）也是合法的，新括号自己也合法，不是的话显然只有（父亲的加上刚匹配的合法

然后从上往下搜索即可

记得处理边界

#include<iostream>
#include<cstdio>
#include<stack>
using namespace std;
int v[500001];
int head[500001];
int ans[500001];
int fa[500001]; 
struct b{
    int to;
    int ne;
}e[500001];
int p;
stack <int>s;//记得long long 
int n;
char c;
int x;
void add(int f,int to){
    p++;
    e[p].ne=head[f];
    e[p].to=to;
    head[f]=p;
    return ;
}
void dfs(int f,int now){
    int fl=0;
    if(s.empty()){
        s.push(now);
        ans[now]=ans[f];
    }else{
        if(v[now]){
            s.push(now);
            ans[now]=ans[f];
        }else{
            if(v[s.top()]){
                fl=s.top();
                s.pop();
                if(!v[fa[fl]])
                ans[now]=ans[f]+1+ans[fa[fl]]-ans[fa[fa[fl]]];
                //画个图啥的还是好懂了
                //毕竟体面说了，合法序列只有自己，镶嵌，相接 
                else{
                    ans[now]=ans[f]+1;//怎么说匹配了一个 
                } 
            }else{
                s.push(now);
                ans[now]=ans[f];
            }
        }
    }
    for(int i=head[now];i;i=e[i].ne){
        dfs(now,e[i].to);
    }
    if(fl){
        s.push(fl);
    }else{
        if(!s.empty())
        s.pop();
    }
    return ;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        cin>>c;
        if(c=='(') 
        v[i]=1;
    }
    for(int i=1;i<n;++i){
        scanf("%d",&x);
        add(x,i+1);
        fa[i+1]=x;
    }
    dfs(0,1);//其实这一变量没必要 
    for(int i=1;i<=n;++i){
        ans[0]^=(i*ans[i]);
    }
    cout<<ans[0]<<endl;
    return 0;
}