一条链

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

int main() {
    int n;
    string s;
    cin >> n >> s;
    s = " " + s;  // 1-based

    vector<int> dp(n+1, 0);
    vector<int> sum(n+1, 0);
    vector<int> stk;  // 存左括号的位置

    long long ans = 0;

    for (int i = 1; i <= n; i++) {
        if (s[i] == '(') {
            stk.push_back(i);
            dp[i] = 0;
        } else { // ')'
            if (!stk.empty()) {
                int pos = stk.back();  // 匹配的左括号位置
                stk.pop_back();
                dp[i] = dp[pos-1] + 1;
            } else {
                dp[i] = 0;
            }
        }
        sum[i] = sum[i-1] + dp[i];
        ans ^= (1LL * i * sum[i]);
    }

    cout << ans << endl;
    return 0;
}

50pts

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int n;
char s[N];
int fa[N],dp[N];

int fun(string t){
	
	int m=t.size();
	int ans=0;
	for(int l=0;l<m;l++){
		int cnt=0;
		for(int r=l;r<m;r++){
			if(t[r]=='(') cnt++;
			else cnt--;
			if(cnt<0) break;
			if(cnt==0) ans++; 
		}
	}return ans;
}
int main(){
	scanf("%d",&n);
	
	for(int i=1;i<=n;i++) cin>>s[i];
	for(int i=2;i<=n;i++) cin>>fa[i]; 
	fa[1]=0;
	
	int ant=0;
	for(int i=1;i<=n;i++){
		string t="";
		int u=i;
		
		//获取从i到1的字符串 
		while(u){
			t+=s[u];
			u=fa[u];
		}reverse(t.begin(),t.end());
		
		//通过栈求字符串匹配
		int k=fun(t);
		
		ant=ant^(i*k);
		
	}
	printf("%d",ant);
	return 0;
}

O(n)

1.考虑统计前$i$点合法子串的个数 $f[i]$，这昂以s[i]结尾的合法序列个数为f[i]-f[p[i]]+1。

2.求 f[i]的过程可以用递推的思想，配合栈的数据结构。我们在深度优先遍历的过程中，如果当前结点为左括号，当前结点的编号进栈;如果为右括号且不空，则可以取出顶的编号，和当前结点配对。

3.递归结束前，恢复之前的栈结构(恢复现场)。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=500010;
vector<int> g[N];
int n;
int p[N];
char str[N];
LL f[N];
int stk[N],top;
void dfs(int u)
{
    if(str[u]=='(')
    {
        stk[++top]=u; //入栈
        f[u]=f[p[u]]; //一定不能选(等价于前面所有字符构成的合法序列方案)
        for(auto x:g[u]) //递归处理
        {
            dfs(x);
        }
        top--; //恢复现场
    }
    else
    {
        if(!top) //没有左括号(不匹配)
        {
            f[u]=f[p[u]];
            for(auto x:g[u])
            {
                dfs(x);
            }
        }
        else
        {
            int t=stk[top--]; //当前匹配的位置
            f[u]=f[p[u]]+f[p[t]]-f[p[p[t]]]+1; 
            //原来的加上p[t]结尾的合法序列的个数
            for(auto x:g[u])
            {
                dfs(x);
            }
            stk[++top]=t;
        }
    }
}
int main()
{
    cin>>n>>str+1;
    for(int i=2;i<=n;i++)
    {
        cin>>p[i];
        g[p[i]].push_back(i); //p[i]可以走到的点是i
    }
    dfs(1);
    LL res=0;
    for(int i=1;i<=n;i++) //根据题目描述求解
    {
        res=res^(i*f[i]);
    }
    cout<<res;
    return 0;
}