先考虑线性的情况
.....(....)
如果是(则将其左边的答案加入栈,这个点的答案为0
如果是)则将栈顶左边的答案+1作为贡献(答案)
每个点的答案为以这个点为右端点的字串的个数
统计答案时前缀和即可
书上的同理，将“左边”改为“父节点”
注意回溯和栈是空的的情况
点击查看代码
#include <vector>
#include <stdio.h>
#include <string.h>
const int N = 5e5 + 5;
typedef long long LL;
std::vector<int> sons[N];
int n, fa[N], stk[N], top;
char str[N];
int res[N];
LL now, ans;
void dfs(int u) {
int tmp = -1;
if(str[u] == '(') stk[++ top] = res[fa[u]];
else if(top) res[u] = (tmp = stk[top]) + 1, top --;
for(int v : sons[u]) dfs(v);
if(str[u] == '(') top --;
else if(tmp != -1) stk[++ top] = tmp;
}
void calc(int u) {
now += res[u], ans ^= u * now;
for(int v : sons[u]) calc(v);
now -= res[u];
}
int main() {
scanf("%d%s", &n, str + 1);
for(int i = 2; i <= n; i ++)
scanf("%d", fa + i), sons[fa[i]].push_back(i);
dfs(1), calc(1), printf("%lld\n", ans);
return 0;
}