~~成功看错题目，对着错误题意调三个小时，最终爆零，成功退役~~
首先，你大可用主席树或者线段树分治通过此题，但是此题存在$O(N)$做法
首先考虑链的做法：先考虑怎么统计在字符串$[l, r]$中，以$i$为$r$的合法字符串个数，~~这就是我考场理解的题意~~，对于一个形如$(……)(……)(……$的合法字符串，以这个字符串的结尾$i$为右端点对答案产生的贡献为前面有多少个已经匹配的括号
比如我刚刚举的例子，那么我们新加入一个$)$，对答案会产生$3$的贡献
于是链上的做法就是每次匹配一个括号，就把栈顶弹出，并将新的栈顶权值$+1$（权值表示以i为开头的形如$(……)$的数量），直接更新答案即可，会发现$(((()))))$这样的括号序列的影响已经消去了
考虑拓展到树上，你大可使用主席树维护，但发现每次我们至多只会修改栈中一个元素，记录下来在回溯的时候改回来即可，总复杂度$O(N)$
附上只改了少处地方的考场代码：
```
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define re register
#define rep(i, a, b) for(re int i = a; i <= b; ++ i)
#define Next(i, u) for(re int i = head[u]; i; i = e[i].next)
il int read() {
re int x = 0, f = 1; re char c = getchar();
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar();
return x * f;
}
#define maxn 500005
int n, head[maxn], cnt, ans[maxn], St[maxn], Top, Val[maxn];
struct edge {
int v, next;
}e[maxn];
char c[maxn];
long long Ans;
il void add(int u, int v) {
e[++ cnt] = (edge){v, head[u]}, head[u] = cnt;
}
il void solve1(int u) {
int flag = 0;
if(c[St[Top]] == '(' && c[u] == ')') flag = St[Top], -- Top, ++ Val[St[Top]], ans[u] += Val[St[Top]];
else St[++ Top] = u;
Next(i, u) ans[e[i].v] = ans[u]/*被这句话送退役了*/, solve1(e[i].v);
if(flag) -- Val[St[Top]], St[++ Top] = flag;
else -- Top;
}
signed main() {
n = read(), scanf("%s", c + 1);
rep(i, 2, n) add(read(), i);
solve1(1);
rep(i, 1, n) Ans ^= i * ans[i];
printf("%lld", Ans);
return 0;
}
```