序列型（55 分）

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500000;
int n;
string s;
stack<int> sta;        // 左括号对应下标
int lst[MAXN + 5];     // 右括号匹配的左括号下标
long long f[MAXN + 5]; // 以 s[i] 为右端点的合法子串数量
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    cin >> s;
    s = "^" + s + "$";
    long long nowAns = 0; // 前缀合法子串数量
    long long ans = 0;    // 最终答案
    for (int i = 1; i <= n; i++)
    {
        if (s[i] == '(')
            sta.push(i);
        else if (!sta.empty())
        {
            lst[i] = sta.top();
            sta.pop();
            f[i] = f[lst[i] - 1] + 1;
        }
        nowAns += f[i];
        ans = ans ^ (i * nowAns);
    }
    cout << ans;
    return 0;
}

树上

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500000;
int n;
string s;
stack<int> sta;        // 左括号对应下标
int lst[MAXN + 5];     // 右括号匹配的左括号下标
long long f[MAXN + 5]; // 以 s[i] 为右端点的合法子串数量
//---树上---
int tot;
char ss[MAXN + 5];
vector<int> e[MAXN + 5];
long long nowAns, ans;
void dfs(int i)
{
    // 之前基础上增加 s[i]
    tot++;
    ss[tot] = s[i];
    if (ss[tot] == '(')
        sta.push(tot);
    else if (!sta.empty())
    {
        lst[tot] = sta.top();
        sta.pop();
        f[tot] = f[lst[tot] - 1] + 1;
    }
    nowAns += f[tot];
    // 调试语句，查看当前序列与算出的合法子串数量
    // for (int u = 1; u <= tot; u++)
    //     cout << ss[u];
    // cout << ":" << nowAns << "\n";
    // 注意 tot 只是根节点到 i 的序列中，节点 i 对应的下标
    // i 才是真实节点编号
    ans = ans ^ (i * nowAns);
    // 处理子节点
    for (int ii : e[i])
        dfs(ii);
    // 去掉 s[i]
    if (ss[tot] == '(')
        sta.pop();
    else if (lst[tot] != 0)
    {
        sta.push(lst[tot]);
        lst[tot] = 0;
    }
    nowAns -= f[tot];
    f[tot] = 0; // 这个很重要，也可以在前面的左括号时把这个改为 0
    tot--;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    cin >> s;
    s = "^" + s + "$";
    for (int v = 2; v <= n; v++)
    {
        int u;
        cin >> u;
        e[u].push_back(v);
    }
    nowAns = 0; // 前缀合法子串数量
    ans = 0;    // 最终答案
    dfs(1);
    cout << ans;
    return 0;
}