维护栈,分讨入栈字符/栈内左括号数量解题

#include<bits/stdc++.h>
using namespace std;

const long long N = 5e5+5;

long long ans[N];
long long n;
bool tag[N];

struct E
{
	int v, pre;
};
int head[N], len;
E e[N<<1];
inline void addedge(int u, int v)
{
	e[++len].v = v; e[len].pre = head[u]; head[u] = len;
}

inline void dfs(long long u, long long l, long long k, long long fa)
{
	//从1到u的路程中,目前栈内有l个左括号,有k个相连的子串,父节点为fa 
	//先计算ans[u], 子节点的sl, 子节点的sk 
	long long sk = 0, sl = 0;
	if(tag[u]) {
		//右括号
		if(l < 1) {//断点 
			sl = 0;
			sk = 0;
			ans[u] = ans[fa];
		}
		else if(l == 1) {//结束一块合法括号串,此时有必要算一下多拼括号串的贡献 
			sl = 0;
			sk = k+1;
			ans[u] = ans[fa] + k + 1;
		}
		else {//l > 1 //什么都没有结束,拼出来一个括号 
			sl = l-1;
			sk = k;
			ans[u] = ans[fa] + 1;
		}
	}
	else {
		//左括号
		sl = l+1;
		sk = k;
		ans[u] = ans[fa];
	}
	//在对子节点下放
	for(long long i = head[u]; i; i = e[i].pre) {
		const long long v = e[i].v;
		if(v == fa) continue;
		dfs(v, sl, sk, u);
	}
}

int main()
{
	ios :: sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	freopen("P5658_3.in", "r", stdin);
	
	cin >> n;
	char ch;
	for(long long i = 1; i <= n; i++) {
		cin >> ch;
		tag[i] = ch - '(';
	}
	for(int i = 2, u; i <= n; i++) {
		cin >> u;
		//可能是我没读懂题目的缘故
		//这个真的需要有向图吗 
		addedge(u, i);
	}
	
	dfs(1, 0, 0, 0);
	
	long long iter = ans[1];
	for(long long i = 2; i <= n; i++) {
		iter = (iter) ^ (ans[i]*i);
	}
	cout << iter << endl;
	
	return 0;
}