题目背景
本题中合法括号串的定义如下：
()是合法括号串。- 如果
A是合法括号串，则(A)是合法括号串。 - 如果
A，B是合法括号串，则AB是合法括号串。
本题中子串与不同的子串的定义如下：
-
字符串 S的子串是S中连续的任意个字符组成的字符串。S的子串可用起始位置 $l$ 与终止位置 $r$ 来表示，记为 $S (l, r)$（$1 \leq l \leq r \leqS $，$ S $ 表示 S 的长度）。 S的两个子串视作不同当且仅当它们在S中的位置不同，即 $l$ 不同或 $r$ 不同。
题目描述
一个大小为 $n$ 的树包含 $n$ 个结点和 $n - 1$ 条边，每条边连接两个结点，且任意两个结点间有且仅有一条简单路径互相可达。
小 Q 是一个充满好奇心的小朋友，有一天他在上学的路上碰见了一个大小为 $n$ 的树，树上结点从 $1 \sim n$ 编号，$1$ 号结点为树的根。除 $1$ 号结点外，每个结点有一个父亲结点，$u$（$2 \leq u \leq n$）号结点的父亲为 $f_u$（$1 ≤ f_u < u$）号结点。
小 Q 发现这个树的每个结点上恰有一个括号，可能是( 或)。小 Q 定义 $s_i$ 为：将根结点到 $i$ 号结点的简单路径上的括号，按结点经过顺序依次排列组成的字符串。
显然 $s_i$ 是个括号串，但不一定是合法括号串，因此现在小 Q 想对所有的 $i$（$1\leq i\leq n$）求出，$s_i$ 中有多少个互不相同的子串是合法括号串。
这个问题难倒了小 Q，他只好向你求助。设 $s_i$ 共有 $k_i$ 个不同子串是合法括号串， 你只需要告诉小 Q 所有 $i \times k_i$ 的异或和，即： \((1 \times k_1)\ \text{xor}\ (2 \times k_2)\ \text{xor}\ (3 \times k_3)\ \text{xor}\ \cdots\ \text{xor}\ (n \times k_n)\) 其中 $xor$ 是位异或运算。
输入格式
第一行一个整数 $n$，表示树的大小。
第二行一个长为 $n$ 的由( 与) 组成的括号串，第 $i$ 个括号表示 $i$ 号结点上的括号。
第三行包含 $n − 1$ 个整数，第 $i$（$1 \leq i \lt n$）个整数表示 $i + 1$ 号结点的父亲编号 $f_{i+1}$。
输出格式
仅一行一个整数表示答案。
样例 #1
样例输入 #1
5
(()()
1 1 2 2
样例输出 #1
6
提示
【样例解释1】
树的形态如下图：
将根到 1 号结点的简单路径上的括号，按经过顺序排列所组成的字符串为 (，子串是合法括号串的个数为 $0$。
将根到 2 号结点的字符串为 ((，子串是合法括号串的个数为 $0$。
将根到 3 号结点的字符串为 ()，子串是合法括号串的个数为 $1$。
将根到 4 号结点的字符串为 (((，子串是合法括号串的个数为 $0$。
将根到 5 号结点的字符串为 (()，子串是合法括号串的个数为 $1$。
【数据范围】
题解
根据合法括号的性质，可以使用栈进行维护，若出现 $($ 与 $)$ 相邻的情况则表明这是一个基础合法状态，可以直接弹出。因而该问题就是在树上进行栈维护。
考虑节点状态转移的过程：
- 若栈内没有元素，且即将压入的字符为 $)$ ，则无需压入直接跳过即可，否则会影响后续的计算；
- 若栈内有元素，且即将压入的字符为 $)$ ，考虑：
- 栈顶元素为 $($ ，栈顶弹出，计算合法括号值（见第四大点）；
- 栈顶元素为 $)$ ，则栈内不可能存在 $($ ，即栈内全为 $)$ ，这与第一大点不符，因此不存在栈顶元素为 $)$ 的情况；
- 若即将压入的元素为 $($ ，直接压入；
- 计算转移：
- 合法括号栈顶元素为$($ ，表明栈中元素全为 $($ ；
- 新增加一个合法括号 $(\ )$ ，考虑其余前者的关系，若形如 $A(\ )$ ，则相当于增加了 $f(A) + 1$ 个合法括号串，其中 $f(A)$ 表示 $A$ 中以最后一个半括号为尾的合法括号的数量（例如 $A=(())()$ 中的 $f(A)$ 为 $2$ ：$\textcolor{red}{(())()},\ (())\textcolor{red}{()}$）；
- 该点处新的合法括号的总量为 $sum[fa[u]] + f[u]$ ；
- 回溯：注意将弹出或压入的元素重新压入或弹出。
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
typedef long long ll;
int n;
string s;
int fa[N];
vector<int> G[N];
int st[N], top;
ll f[N], k[N];
void dfs(int u) {
int tmp = 0;
if (s[u] == ')') {
if (top) {
tmp = st[top--];
f[u] = f[fa[tmp]] + 1;
}
}
else st[++top] = u;
k[u] = k[fa[u]] + f[u];
for (int v : G[u]) dfs(v);
if (tmp) st[++top] = tmp;
else if (top) --top;
}
int main() {
cin >> n >> s;
s = ' ' + s;
for (int i = 2;i <= n;i++) {
int u; cin >> u;
fa[i] = u;
G[u].push_back(i);
}
dfs(1);
ll res = 0;
for (int i = 1;i <= n;i++) {
res ^= (1LL * i * k[i]);
}
cout << res << '\n';
return 0;
}