本来想出一个O(n)的算法，见程序最下边蓝字。迅速码完然后WA了

我觉得应该是细节问题，然后我就打算先打个暴力（思路本质上跟蓝字一样），最坏复杂度是O($n^2$)，结果居然秒A了... ...

#include <iostream>
#include <cstdio>
#include <string>
using namespace std;

#define int long long

const int N=500005;

struct E {int nex,to;} e[N];
int n,num,ans;
int v[N],h[N],k[N],f[N],pa[N],c[N];

int read() {
	int x=0; char c=getchar();
	while(c<'0' || c>'9') c=getchar();
	while(c>='0' && c<='9') {x=x*10+c-'0'; c=getchar();}
	return x;
}
void add(int u,int v) {e[++num]={h[u],v},h[u]=num;} 

int cal(int x) {
	int v1=0,v2=0;
	while(1) {
		if(!v[x]) v1++;
		else v2++;
		if(v1>=v2) return x;
		x=pa[x];
		if(!x) return -1;
	}
}

void dfs(int x) {
	for(int i=h[x];i;i=e[i].nex) {
		int son=e[i].to;
		if(!v[son]) {dfs(son); continue;}
		int last=cal(son);
		if(last==-1) {dfs(son); continue;}
		f[son]=1+f[pa[last]];
		dfs(son);
	} 
}

void out(int x) {
	for(int i=h[x];i;i=e[i].nex) {
		int son=e[i].to,fat=x;
		f[son]+=f[fat];
		ans=(ans^(son*f[son]));
		out(son);
	}
}

signed main()
{
	cin>>n;
	string t; cin>>t;
	for(int i=0;i<t.size();i++)
		if(t[i]==')') v[i+1]=1;
	for(int i=2;i<=n;i++) {
		int v=read();
		add(v,i);
		pa[i]=v;
	}
	dfs(1);
	out(1);
	cout<<ans;
	return 0;
}
/*
	令'('为0，')'为1
	令f[i]为结点i的答案
	令a[i]为i到根节点0的个数（不包括自己） 
	令b[i]为i到根节点1的个数（不包括自己） 
	令c[i]为a[i]-b[i] 
	令k[i]为从后往前第一个满足c[k]<c[i]的位置k
	
	易证c[i]=c[i.fat]+(1/-1)，所以
		若c[i.fat]<c[i], k[i]=i.fat
		若c[i.fat]>c[i], k[i]=k[k[i.fat]]
	对于i，若为右括号1，f[i] = 1 + f[k[i].fat]
	对于i，若为左括号0，f[i] = f[i.fat]
	
	a[], b[]可以O(n)预处理 
*/