C. 括号序列

题目描述

这是一道字符串题。

相信大家都有听说过括号序列。

在本题，括号序列指的是只由 $(，)$组成的字符串。

一个好的括号序列归纳定义如下：

归纳基：() 是一个好的括号序列

归纳步：若 $A,B$ 都是好的括号序列，那么 (A) 和 AB 都是好的括号序列。

例如，(()())() 是一个好的括号序列；)(()()() 是括号序列，但不是一个好的括号序列；(aasdfa(Asd)) 不是一个括号序列。

现在你有一棵 $n$ 个点， $n-1$ 条边，以 $1$ 为根的有根树；树上的每个节点 $x$ 都有一个括号 $a_x$ = ( 或 ) 。

现定义一个点 $x$ 对应的字符串 $p_x$ 为从根开始依次经过最短路径到 $x$ 的所有节点括号的顺序拼接。

形式上：

$1.$ $p_1 = a_1$

$2. p_x=p_{f_x} + a_x$ ，其中 $f_x$ 为 $x$ 的父亲，$+$ 表示拼接操作。

现在对于每一个 $p_x$ 求有多少个子串是好的括号序列。

输入描述

第一行一个正整数 $n$ 表示树的点数。

第二行一个长度为 $n$ 的括号序列表示 $a$ 。

第三行一个长度为 $n-1$ 的正整数序列 $f'$。表示 $f_{i+1}=f'_i$ 。

输出描述

为了减少输出规模，请输出 $(x*ans_x)$ 异或和。

即：$(1*ans_1) \^{\space} (2*ans_2) \^{\space} (3*ans_3) \^{\space} ... \^{\space} (n*ans_n)$

输入样例

7
(()()((
1 2 3 4 5 6

输出样例

15

数据范围

对于 $10\%$ 的数据，满足 $n\leq 8,f_i=i-1$

对于 $20\%$ 的数据，满足 $n\leq 200,f_i=i-1$

对于 $30\%$ 的数据，满足 $n\leq 2000,f_i=i-1$

对于 $50\%$ 的数据，满足 $n\leq 10^5,f_i=i-1$

对于另外 $20\%$ 的数据，满足 $n\leq 2000$

对于另外 $20\%$ 的数据，满足 $n\leq 10^5$

对于另外 $10\%$ 的数据，满足 $n\leq 5*10^5$