A42 正经题解

题意分析
给定一颗树，每个节点上有一个左或右括号，设1到$i$节点的简单路径中有$cnt_i$个子串为合法括号子串，求出所有$cnt_i \times i$的异或和。
具体思路
参考普通括号序列计数$dp$，括号序列的状态可以分为两种，一种是不可分割为两个合法序列的，即（A），一种是可以分割为两个合法序列的，即AB。
定义$dp_i$为到节点$i$为止，路径上所有不同合法子串的总数（即所有位置结尾的合法子串数量之和），$cnt_i$为以节点$i$结尾的连续不可分割的合法序列个数。
对于每个节点$i$，其父节点为$f$：
如果是左括号，则无法为合法字串数量做出贡献，将$i$放入栈中准备匹配。
如果是右括号，则检测栈中是否有等待匹配的左括号，如果栈顶有左括号节点$j$，则弹出$j$，使$cnt_i = cnt_j+1$，$dp_i=cnt_i+dp_f$。
否则，无法做出贡献，因为是右节点，所以也无法放入栈中匹配。
回溯是很重要的一步，如果不进行回溯，父节点进行其他路径的搜索时栈中会仍有上条路径还未匹配的左括号节点，搜索时也可能因为父节点作为左括号在上条路径中被匹配导致栈中没有父节点，从而使得右括号匹配不上，计算结果变小。
AC代码

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5+5;
int n;
string s;
vector<int> edge[N];
int fa[N];
long long dp[N];
int cnt[N];
stack<int> stk;
long long ans = 0;

void dfs(int u, int f){
    int last = -1;
    if(s[u]=='('){
        stk.push(u);
        dp[u] = dp[f];
    }else{
        if(!stk.empty()){
            int left = stk.top();
            stk.pop();
            last = left;
            cnt[u] = cnt[fa[left]]+1;
            dp[u] = dp[f]+cnt[u];
        }else{
            dp[u] = dp[f];
        }
    }

    ans ^= (1LL*u*dp[u]);
    for(auto v:edge[u]){
        if(v==f) continue;
        dfs(v, u);
    }
    if(s[u]=='(')
        stk.pop();
    else if(last!=-1)
        stk.push(last);
    return;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> s;
    s = " "+s;
    for(int i=2;i<=n;i++){
        cin >> fa[i];
        edge[fa[i]].push_back(i);
        edge[i].push_back(fa[i]);
    }
    dfs(1, 0);
    cout << ans;

    return 0;
}

时间复杂度
$O(n)$，跑一遍$dfs$就出结果了，但似乎常数因子较大，还有待优化。