记录编号	584446	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[CSP 2019S]括号树	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	0.356 s
提交时间	2023-11-12 20:54:30	内存使用	21.37 MiB

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5+10,M = 1e6+10;
int n;
struct made{
    int ver,nx;
}e[M<<1];
int hd[N],tot;
long long f[N],s[N],fa[N];
char a[N];
void add(int x,int y){
    tot++;
    e[tot].ver = y,e[tot].nx = hd[x],hd[x] = tot;
}
stack<int>st; 
void dfs(int x){
    int u = 0;
    if(a[x] == ')'){
        if(!st.empty()){
            u = st.top();st.pop();
            s[x] = s[fa[u]] + 1;
        }
    }
    else if(a[x] == '(')st.push(x);
    f[x] = f[fa[x]] + s[x];
    for(int i = hd[x];i;i = e[i].nx)dfs(e[i].ver);
    //回溯
    if(u != 0)st.push(u);
    else if(!st.empty())st.pop();
}
int main(){
    freopen("2019brackets.in","r",stdin);
    freopen("2019brackets.out","w",stdout);
    scanf("%d%s",&n,a+1);
    for(int i = 2;i <= n;i++){
        int x;scanf("%d",&x);
        add(x,i);fa[i] = x;
    }
    dfs(1);
    long long ans = 0;
    for(int i = 1;i <= n;i++){
//        cout<<f[i]<<endl;
        ans = ans ^ ((long long)i * f[i]);
    }
    printf("%lld\n",ans) ;
    
    return 0;
    
}