题目：
1.本题中合法括号串的定义如下：
() 是合法括号串。
如果 A 是合法括号串，则 (A) 是合法括号串。
如果 A，B 是合法括号串，则 AB 是合法括号串。
2.本题中子串与不同的子串的定义如下：
字符串 S 的子串是 S 中连续的任意个字符组成的字符串。
S 的子串可用起始位置 ll 与终止位置 rr 来表示，记为
S (l, r)S(l,r)
( 1 \leq l \leq r \leq |S |1≤l≤r≤∣S∣，|S |∣S∣ 表示 S 的长度）。
S 的两个子串视作不同当且仅当它们在 S 中的位置不同，即 ll 不同或 rr 不同。
以上都是废话，了解即可……
3.注意：
必须开 longlong
longlong 最好写它：
using namespace std;
typedef long long ll;能让长长的 longlong 就写 ll 例如：
ll a;讲解题：
题目：
一个大小为 nn 的树包含 nn 个结点和 n − 1n−1 条边，每条边连接两个结点，且任意两个结点间有且仅有一条简单路径互相可达。
这代表它是 树
图、树我推荐用 盗版 链表存图：
#include<vector>
vector<ll>adj[inf];//声明变量
adj[a].push_back(b);//将b塞到adj[a]里面的最后面的位置如果这道题是线性的话就简单多了！（这样就不是提高组的题了）。
正确解法：
跑一边 DFS 计算当前结点 u 的合法字串数量。
void dfs(ll u,ll father,ll rem){
k[u]+=k[father];//起码有它父亲结点的字串的数量
if(s[u]=='('){
rem++;
ll save=dp[rem];//保留记录
dp[rem]=0;
for(int i=0;i<adj[u].size();i++){
dfs(adj[u][i],u,rem);
}
dp[rem]=save;//写回原数据
}
else{
if(rem==0){
ll save=dp[0];//保留记录
dp[0]=0;
for(int i=0;i<adj[u].size();i++){
dfs(adj[u][i],u,rem);
}
dp[0]=save;//写回原数据
}
else{
rem--;//回溯
k[u]=k[u]+dp[rem]+1;
ll save=dp[rem];//保留记录
dp[rem]++;
for(int i=0;i<adj[u].size();i++){
dfs(adj[u][i],u,rem);
}
dp[rem]=save;//写回原数据
}
}
ans^=u*k[u];//计算异或和
}主函数：输入+存图（树）
int main(){
scanf("%lld%s",&n,(s+1));//(s+1)是读入技巧：让字符串 s 下标从1开始读
for(ll i=2;i<=n;i++){
ll f;
scanf("%lld",&f);
adj[f].push_back(i);//加边
}
dfs(1,0,0);//跑 DFS
printf("%lld\n",ans);
return 0;
}最后
献上完整代码：
#include<iostream>
#include<vector>
#include<cstdio>
using namespace std;
typedef long long ll;
const int inf=500005;
ll n,dp[inf],k[inf],ans;
char s[inf];
vector<ll> adj[inf];
void dfs(ll u,ll father,ll rem){
k[u]+=k[father];//起码有它父亲结点的字串的数量
if(s[u]=='('){
rem++;
ll save=dp[rem];//保留记录
dp[rem]=0;
for(int i=0;i<adj[u].size();i++){
dfs(adj[u][i],u,rem);
}
dp[rem]=save;//写回原数据
}
else{
if(rem==0){
ll save=dp[0];//保留记录
dp[0]=0;
for(int i=0;i<adj[u].size();i++){
dfs(adj[u][i],u,rem);
}
dp[0]=save;//写回原数据
}
else{
rem--;//回溯
k[u]=k[u]+dp[rem]+1;
ll save=dp[rem];//保留记录
dp[rem]++;
for(int i=0;i<adj[u].size();i++){
dfs(adj[u][i],u,rem);
}
dp[rem]=save;//写回原数据
}
}
ans^=u*k[u];//计算异或和
}
int main(){
scanf("%lld%s",&n,(s+1));//(s+1)是读入技巧：让字符串 s 下标从1开始读
for(ll i=2;i<=n;i++){
ll f;
scanf("%lld",&f);
adj[f].push_back(i);//加边
}
dfs(1,0,0);//跑 DFS
printf("%lld\n",ans);
return 0;
}