题目描述

给定一个树，求从根节点到每个节点的括号串中，有多少个合法括号串。

解题思路

链的优化

1. 枚举节点，枚举区间，判断区间合法性（10pts）。

PS：洛谷可以得 20 分。

时间复杂度：$O(n^4)$。

代码如下：

#include<iostream>
using namespace std;
const int N=5e5+10;
int n;
char s[N];
int a[N];
bool legitimate(int l,int r){
	int x=0;
	for(int i=l;i<=r;i++){
		if(s[i]=='(')x++;
		else x--;
		if(x<0)return false;
	}
	return (x==0);
}//判断括号串是否合法 
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>s+1;
	for(int p=1;p<=n;p++){
		for(int l=1;l<p;l++){
			for(int r=l+1;r<=p;r++){
				if(legitimate(l,r))a[p]++;
			}
		}
	}
	long long ans=0;
	for(int i=1;i<=n;i++){
		ans^=(long long)i*a[i];
	}
	cout<<ans<<'\n';
	return 0;
}

2. 容易发现，若区间 $(l,r)$ 是区间 $(1,x)$ 合法子串的合法子串，那么它一定是区间 $(1,x+1)$ 的合法子串。

所以，我们可以定义数组 $g$，$g_i$ 表示以第 $i$ 个字符结尾的合法括号串的数量；再定义数组 $f$，$f$ 为 $g$ 的前缀和，$f_i$ 即区间 $(1,i)$ 的合法子串的数量（20pts）。

时间复杂度：$O(n^3)$。

PS：洛谷可以得 35 分。

代码如下：

#include<iostream>
using namespace std;
const int N=5e5+10;
int n;
char s[N];
int g[N],f[N];
bool legitimate(int l,int r){
	int x=0;
	for(int i=l;i<=r;i++){
		if(s[i]=='(')x++;
		else x--;
		if(x<0)return false;
	}
	return (x==0);
} 
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>s+1;
	for(int l=1;l<n;l++){
		for(int r=l+1;r<=n;r++){
			if(legitimate(l,r))g[r]++;
		}
	}
	for(int i=1;i<=n;i++)f[i]=f[i-1]+g[i];//计算前缀和 
	long long ans=0;
	for(int i=1;i<=n;i++){
		ans^=(long long)i*f[i];
	}
	cout<<ans<<'\n';
	return 0;
}

3. 枚举 $l$，一边枚举 $r$ 一边判断是否合法（35pts）。

时间复杂度：$O(n^2)$。

代码如下：

#include<iostream>
using namespace std;
const int N=5e5+10;
int n;
char s[N];
int g[N],f[N];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>s+1;
	for(int l=1;l<n;l++){
		int x=0;
		for(int r=l;r<=n;r++){
			if(s[r]=='(')x++;
			else x--;
			if(x<0)break;
			else if(x==0)g[r]++;
		}
	}
	for(int i=1;i<=n;i++)f[i]=f[i-1]+g[i];
	long long ans=0;
	for(int i=1;i<=n;i++){
		ans^=(long long)i*f[i];
	}
	cout<<ans<<'\n';
	return 0;
}

4. 重难点：

设与 $s_i$ 匹配的左括号的下标为 $p_i$。

我们可以发现，第 $i$ 个字符可以匹配的字符串，一定包含了 $(p_i,i)$ 这段区间，于是我们可以把第 $i$ 个字符可以匹配的字符串分为两段：以 $p_i-1$ 结尾的合法括号串和区间 $(p_i,i)$，所以我们可以用一个栈存储 $p_i$，进一步推出 $g_i=g_{p_i-1}+1$，从而用线性的复杂度推出每个 $g_i$（55pts）。

时间复杂度：$O(n)$。

代码如下：

#include<iostream>
#include<vector>
using namespace std;
const int N=5e5+10;
vector<int> v[N];
int n;
char s[N];
int fa[N];
long long g[N],f[N];
int stk[N],top;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>s+1;
	for(int i=2;i<=n;i++){
		cin>>fa[i];
	}
	for(int i=1;i<=n;i++){
		if(s[i]=='(')stk[++top]=i;
		else{
			if(top)g[i]=g[stk[top--]-1]+1;//计算贡献 
		}
		f[i]=f[i-1]+g[i];
	} 
	long long ans=0;
	for(int i=1;i<=n;i++){
		ans^=(long long)i*f[i];
	}
	cout<<ans<<'\n';
	return 0;
}

化链为树

有了链的线性做法，我们不难想出树上的做法（因为树可以转化为多条链），我们可以采用深度优先搜索来遍历树。

我们需解决两个难题：

• $g$ 数组和 $f$ 数组的求法。
• dfs 的回溯。

对于第一个难题，我们可以想，之所以在链时我么可以用 $g_i=g_{p_i-1}+1,f_i=f_{i-1}+g_i$ 的式子，是因为题目保证了节点编号是连续的，而 $i-1$ 是 $i$ 的父节点，即 $fa_i$。

所以我们只需把 $g_i=g_{p_i-1}+1,f_i=f_{i-1}+g_i$ 改成 $g_i=g_{fa_{p_i}}+1,f_i=f_{fa_{i-1}}+g_i$ 即可。

对于第二个难题，我们不难发现，在 dfs 的过程中，我们只需要还原存储左括号下标的栈即可。

这样，问题就得到了完美地解决（100pts）。

时间复杂度：$O(n)$。

代码如下：

#include<iostream>
#include<vector>
using namespace std;
const int N=5e5+10;
vector<int> v[N];
int n;
char s[N];
int fa[N];
long long g[N],f[N];
int stk[N],top;
void dfs(int x){
	int tmp=0;
	if(s[x]=='('){
		stk[++top]=x;
	}
	else{
		if(top){
			tmp=stk[top];
			g[x]=g[fa[tmp]]+1;//计算贡献
			top--;
		}
	}
	f[x]=f[fa[x]]+g[x];//计算前缀和
	for(int i=0,len=v[x].size();i<len;i++){
		dfs(v[x][i]);
	}
	if(tmp)stk[++top]=tmp;
	else if(top)top--;//回溯
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>s+1;
	for(int i=2;i<=n;i++){
		cin>>fa[i];
		v[fa[i]].push_back(i);
	}
	dfs(1);
	long long ans=0;
	for(int i=1;i<=n;i++){
		ans^=(long long)i*f[i];
	}
	cout<<ans<<'\n';
	return 0;
}

总结

对于这种树上问题，我们可以先考虑链的做法，在逐步推广到树，最终得到正确的解法。

希望这篇题解能帮助到大家。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=5e5+10;
char c[N];
vector<int>G[N];
int n,fa[N],p[N],a[N];LL s[N];
void dfs(int x)
{
    if(c[x]=='(')p[x]=x;
    else
    {
        if(p[fa[x]])a[x]=a[fa[p[fa[x]]]]+1,p[x]=p[fa[p[fa[x]]]];
    }

    s[x]=s[fa[x]]+a[x];

    for(int y:G[x])
        dfs(y);
}
int main()
{
    scanf("%d%s",&n,c+1);
    for(int i=2,x;i<=n;i++)
    {
        scanf("%d",&x);fa[i]=x;
        G[x].push_back(i);
    }
    memset(p,0,sizeof(p));
    memset(a,0,sizeof(a));
    memset(s,0,sizeof(s));
    dfs(1);
    LL ans=0;
    for(int i=1;i<=n;i++) ans^=s[i]*i;
    printf("%lld\n",ans);
    return 0;
}