题目描述
本题中合法括号串的定义如下：
-
() 是合法括号串。
-
如果 A 是合法括号串，则 (A) 是合法括号串。
-
如果 A，B 是合法括号串，则 AB 是合法括号串。
本题中子串与不同的子串的定义如下：
-
字符串 S 的子串是 S 中连续的任意个字符组成的字符串。S 的子串可用起始位置 l 与终止位置 r 来表示，记为 S(l,r)（1≤l≤r≤|S|，|S| 表示 S 的长度）。
-
S 的两个子串视作不同当且仅当它们在 S 中的位置不同，即 l 不同或 r 不同。
一个大小为 n 的树包含 n 个结点和 n−1条边，每条边连接两个结点，且任意两个结点间有且仅有一条简单路径互相可达。
小 Q 是一个充满好奇心的小朋友，有一天他在上学的路上碰见了一个大小为 n 的树，树上结点从 1 ∼ n 编号，1 号结点为树的根。
除 1 号结点外，每个结点有一个父亲结点，u（2≤u≤n）号结点的父亲为 fu（1≤fu<u）号结点。
小 Q 发现这个树的每个结点上恰有一个括号，可能是( 或)。
小 Q 定义 si 为：将根结点到 i 号结点的简单路径上的括号，按结点经过顺序依次排列组成的字符串。
显然 si 是个括号串，但不一定是合法括号串，因此现在小 Q 想对所有的 i (1≤i≤n) 求出，si 中有多少个互不相同的子串是合法括号串。
这个问题难倒了小 Q，他只好向你求助。
设 si 共有 ki 个不同子串是合法括号串，你只需要告诉小 Q 所有 i×ki 的异或和，即：
(1×k1)xor(2×k2)xor(3×k3)xor⋅⋅⋅xor(n×kn)
其中 xor 是位异或运算。
输入格式
第一行一个整数 n，表示树的大小。
第二行一个长为 n 的由 ( 与 ) 组成的括号串，第 i 个括号表示 i 号结点上的括号。
第三行包含 n−1 个整数，第 i（1≤i<n）个整数表示 i+1 号结点的父亲编号 fi+1。
输出格式
仅一行一个整数表示答案。
样例
输入样例
5
(()()
1 1 2 2
输出样例
6
算法1
(DFS+栈模拟) $O(n)$
首先分析题面，分析题面很重要，因为考场上因为括号匹配的规则没读明白导致QAQ。所以，一定要读明白题目。
根据题面的意思，我们可以先求出每个节点到根节点的合法括号数。
现在先设定一个f数组，f[i]代表i到根节点有多少合法括号数。判断括号序列是否合法跟之前有一题叫做括号画家比较相似。
左括号直接入栈，遇到右括号再出栈，根据这个性质来求有多少合法序列，那么也能得到合法个数只在读到右括号时才会有改变。那么可以想一下递推的公式。
如果i为右括号，那么f[i]应该怎么变？
第一步可以先思考一下i是从他父亲过来的，即f[i]=f[i的父亲]+以i为右边界时的合法括号数量。
那么现在就转化为了一个递归问题。
现在再次思考一个问题，就是如何求出以i为右边界时的合法括号数量？
现在假设有一串括号
根据以i为右边界最后一个合法括号的左括号位置为j+1那么以i为右边界的合法括号数就比以j结尾的合法括号数多1。
所以就可以根据这个性质去进行更新f数组。存储以i为右边界时的合法括号数量可以开一个g数组，根据上图可得到等式g[i]=g[j]+1;j为栈顶元素的父亲。这样就可以求出咱们所要的以i为右边界时的合法括号数量。有了这些性质，就可以直接dfs然后进行更新，得到i到根节点的所有合法括号个数。
参考文献
敬请观看y总视频讲解
C++ 代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
char s[500010];
int ver[500010],head[500010],ne[500010],tot=0;
int f[500010],g[500010],p[500010];
stack<int>st;
void add(int x,int y)
{
ver[++tot]=y;
ne[tot]=head[x];
head[x]=tot;
}
void dfs(int x)
{
if(s[x]=='(')
{
st.push(x);
f[x]=f[p[x]];
for(int i=head[x];i;i=ne[i])
{
int y=ver[i];
dfs(y);
}
st.pop();
}
else
{
if(st.empty())
{
f[x]=f[p[x]];
for(int i=head[x];i;i=ne[i])
{
int y=ver[i];
dfs(y);
}
}
else
{
int t=st.top();
st.pop();
g[x]=g[p[t]]+1;
f[x]=f[p[x]]+g[x];
for(int i=head[x];i;i=ne[i])
{
int y=ver[i];
dfs(y);
}
st.push(t);
}
}
}
signed main()
{
int n;
cin>>n;
cin>>s+1;
for(int i=2;i<=n;i++)
{
cin>>p[i];
add(p[i],i);
}
// for(int i=1;i<=n;i++)
// cout<<p[i]<<' ';
dfs(1);
int res=0;
for(int i=1;i<=n;i++)
{
res^=i*f[i];
}
cout<<res;
}
