#include <bits/stdc++.h>
#define N 500005
using namespace std;
typedef long long ll;
//父亲数组和待匹配链
int n, fat[N], pre[N];
//向上连续的不可分割合法序列个数,总合法序列个数
ll smh[N], num[N], ans;
//总合法序列最多n^2个,所以要开ll。
//前向星
int head[N], to[N], nxt[N], cnt = 1;
char str[N];
void addedge(int u, int v) {
to[cnt] = v;
nxt[cnt] = head[u];
head[u] = cnt++;
}
void dfs(int p, int lst) {
num[p] = num[fat[p]];//继承
if(str[p] == '(') {
pre[p] = lst;
lst = p;//加入链表待匹配
} else {
if(lst) {//存在等待匹配的左括号
smh[p] = smh[fat[lst]] + 1;//连续数+1
num[p] += smh[p];//对答案贡献(产生新smh[p]个合法序列)
lst = pre[lst];//最后一个已匹配,删出链表
}
}
ans ^= (ll)p * num[p];//加入结果
for(int i = head[p];i;i = nxt[i])
dfs(to[i], lst);
}
int main() {
scanf("%d%s", &n, str + 1);//编号1-n,记得+1
for(int i = 2;i <= n;i++) {
scanf("%d", fat + i);
addedge(fat[i], i);
}
dfs(1, 0);
printf("%lld", ans);
return 0;
}
题目链接