[CSP-S 2019]括号树

源代码：

#include<cstdio>

#include<cctype>

#include<vector>

inline int getint() {

	register char ch;

	while(!isdigit(ch=getchar()));

	register int x=ch^'0';

	while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');

	return x;

}

inline bool isbracket(const char &ch) {

	return ch=='('||ch==')';

}

inline bool getbracket() {

	register char ch;

	while(!isbracket(ch=getchar()));

	return ch==')';

}

typedef long long int64;

const int N=5e5+1;

std::vector<int> e[N];

inline void add_edge(const int &u,const int &v) {

	e[u].push_back(v);

}

bool c[N];

int stk[N],par[N],dep[N],top[N];

int64 f[N];

void dfs(const int &x) {

	dep[x]=dep[par[x]]+1;

	stk[dep[x]]=x;

	//f[x]: end with current char

	if(x!=1&&c[x]&&!c[par[x]]) {//"..." + "()"

		f[x]=1+f[par[par[x]]];

		top[x]=top[par[par[x]]]?:par[x];

	}

	if(x!=1&&c[x]&&c[par[x]]) {//"(" + "(...)" + ")"

		if(top[par[x]]>1&&!c[par[top[par[x]]]]) {

			f[x]=1+f[par[par[top[par[x]]]]];

			top[x]=top[par[par[top[par[x]]]]]?:par[top[par[x]]];

		}

	}

	for(unsigned i=0;i<e[x].size();i++) {

		dfs(e[x][i]);

	}

}

int main() {

	freopen("brackets.in","r",stdin);

	freopen("brackets.out","w",stdout);

	const int n=getint();

	for(register int i=1;i<=n;i++) {

		c[i]=getbracket();

	}

	for(register int i=2;i<=n;i++) {

		par[i]=getint();

		add_edge(par[i],i);

	}

	dfs(1);

	for(register int i=2;i<=n;i++) {

		f[i]+=f[par[i]];

	}

	int64 ans=0;

	for(register int i=1;i<=n;i++) {

		ans^=f[i]*i;

	}

	printf("%lld\n",ans);

	return 0;

}