【正经题解】括号树

注意到每次加入新括号都是在区间尾，并且合法括号序列只有两种：

不可分割合法序列： 不可拆分的合法序列，即左端点与右端点相匹配的合法序列。

组合合法序列： 由多个 连续的 不可拆分合法序列组合而成的合法序列。

于是，如果末尾加入的括号要对合法序列个数的增加有贡献，那么需要满足：

1. 是右括号

2. 左边有等待匹配的左括号

如果满足上述条件，那么这一对括号匹配后就会成为一个 不可分割合法序列 ，剩下的贡献就是考虑这个子序列与其他子序列合并后的贡献了，注意到合并后的新序列一定是一个 连续的 ， 包含末尾 的序列，所以记录每个点向左 连续的 不可分割合法序列有多少个就行了。

这样，当前区间左匹配点之前连续的每一个不可分割合法序列的左端点到末尾就又是一个组合合法序列，由于记录了连续的个数，所以计算贡献是 O(1) 的。

而对于等待匹配的左括号，可以用链表或者栈维护。

同理，不难推广到树上的每条链，复杂度 O(n) 。

如果是栈维护，回溯时还没匹配的记得退栈，这里是链表实现。

#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;
}