10pts dfs写法

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
const int N=5e5;
char a[N];
char s[N];
int f[N];
int nxt[N],to[N],head[N];
long long sum[N];
long long lst[N];
long long ans=0;
int top,cnt;
void edge_add(int u,int v){
    nxt[++cnt]=head[u];
	head[u]=cnt;
	to[cnt]=v;
}
inline void dfs(int x){
	int tmp=0;
	if(a[x]==')'){
		if(top){
			tmp=s[top];
			lst[x]=lst[f[tmp]]+1;
			--top;
		}
	}
	else if(a[x]=='(') s[++top]=x;
	sum[x]=sum[f[x]]+lst[x];
	for(int i=head[x];i;i=nxt[i]) dfs(to[i]);
	if(tmp!=0) s[++top]=tmp;
	else if(top) --top;
}
signed main(){
    scanf("%lld",&n);
    scanf("%s",a+1);
    for (int i=2;i<=n;++i){
        scanf("%lld",&f[i]);
        edge_add(f[i],i);
    }
    dfs(1);
    for (long long i=1;i<=n;++i){
        ans^=sum[i]*i;
    }
    cout<<ans;
    return 0;
}