$\text{[CSP-S2019] 括号树}$

#include <iostream>
#include <string>
#include <vector>
#include <stack>
using namespace std;
const int N = 5e5 + 5;
int n, f[N];
int sum[N];
string s;
vector<int> g[N];
void dfs(int u, int ft, stack<int> sta) {
    if (s[u] == ')')
        if (!sta.empty()) {
            f[u] = f[sta.top() - 1] + 1;
            sta.pop();
        }
    if (s[u] == '(')    sta.push(u);
    sum[u] = sum[ft] + f[u];
    for (int l = 0; l < g[u].size(); ++l) {
        int i = g[u][l];
        dfs(i, u, sta);
    }
}
signed main() {
    cin >> n >> s;
    s = ' ' + s;
    for (int i = 2; i <= n; ++i) {
        int fa;
        cin >> fa;
        g[fa].push_back(i);
    }
    stack<int> sta;
    dfs(1, 0, sta);
    int ans = 0;
    for (int i = 1; i <= n; ++i)
        ans ^= i * sum[i];
    cout << ans;
    return 0;
}