#790. 括号树

括号树

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

本题中合法括号串的定义如下:

  • 1\red 1. () 是合法括号串;
  • 2\red 2. 如果 A 是合法括号串,则 (A) 是合法括号串。
  • 3\red 3. 如果 AB 是合法括号串,则 AB 是合法括号串。

本题中子串与不同的子串的定义如下:

  • 1\red 1. 字符串 S\red{S} 的子串是 S\red{S} 中连续的任意个字符组成的字符串。S\red{S} 的子串可用起始位置 l\red{l} 与终止位置 r\red{r} 来表示,记为 S(l,r)\red{S (l, r)}1lrS1 \le l \le r \le |S|S\red{|S|} 表示 S\red{S} 的长度)。
  • 2\red 2. S\red{S} 的两个子串视作不同当且仅当它们在 S\red{S} 中的位置不同,即 l\red{l} 不同或 r\red{r} 不同。

一个大小为 n\red{n} 的树包含 n\red{n} 个结点和 n1\red{n - 1} 条边,每条边连接两个结点,且任意两个结点间有且仅有一条简单路径互相可达。

Q\red Q 是一个充满好奇心的小朋友,有一天他在上学的路上碰见了一个大小为 n\red{n} 的树,树上结点从 1n\red{1 \sim n} 编号,1\red{1} 号结点为树的根。除 1\red{1} 号结点外,每个结点有一个父亲结点,u2un\red{u(2 \le u \le n)}号结点的父亲为 fu1fu<u\red{f_u(1 \le f_u < u)}号结点。

Q\red Q 发现这个树的每个结点上恰有一个括号,可能是 ()。小 Q\red Q 定义 si\red{s_i} 为:将根结点到 i\red{i} 号结点的简单路径上的括号,按结点经过顺序依次排列组成的字符串。

显然 si\red{s_i} 是个括号串,但不一定是合法括号串,因此现在小 Q\red Q 想对所有的 i1in\red{i(1 \le i \le n)}求出,si\red{s_i} 中有多少个互不相同的子串是合法括号串。

这个问题难倒了小 Q\red Q,他只好向你求助。设 si\red{s_i} 共有 ki\red{k_i} 个不同子串是合法括号串,你只需要告诉小 Q\red Q 所有 i×ki\red{i \times k_i} 的异或和,即:

(1×k1) xor (2×k2) xor (3×k3) xor  xor (n×kn)\red{(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\red{\text{xor}} 是位异或运算。

输入格式

第一行一个整数 n\red{n},表示树的大小。

第二行一个长为 n\red{n} 的由 () 组成的括号串,第 i\red{i} 个括号表示 i\red{i} 号结点上的括号。

第三行包含 n1\red{n−1} 个整数,第 i1i<n\red{i(1 \le i < n)}个整数表示 i+1\red{i + 1} 号结点的父亲编号 fi+1\red{f_{i+1}}

输出格式

仅一行一个整数表示答案。

样例

输入样例

5
(()()
1 1 2 2

输出样例

6

样例说明

树的形态如下图:

img

将根到 1\red{1} 号结点的简单路径上的括号,按经过顺序排列所组成的字符串为 (,子串是合法括号串的个数为 0\red{0}

将根到 2\red{2} 号结点的简单路径上的括号,按经过顺序排列所组成的字符串为 ((,子串是合法括号串的个数为 0\red{0}

将根到 3\red{3} 号结点的简单路径上的括号,按经过顺序排列所组成的字符串为 (),子串是合法括号串的个数为 1\red{1}

将根到 4\red{4} 号结点的简单路径上的括号,按经过顺序排列所组成的字符串为 (((,子串是合法括号串的个数为 0\red{0}

将根到 5\red{5} 号结点的简单路径上的括号,按经过顺序排列所组成的字符串为 ((),子串是合法括号串的个数为 1\red{1}

提示

测试点编号 n\red{n\le } 特殊性质
12\red{1\sim 2} 8\red{8} fi=i1\red{f_i=i-1}
34\red{3\sim 4} 200\red{200}
57\red{5\sim 7} 2×103\red{2\times 10^3}
810\red{8\sim 10}
1114\red{11\sim 14} 105\red{10^5} fi=i1\red{f_i=i-1}
1516\red{15\sim 16}
1720\red{17\sim 20} 5×105\red{5\times 10^5}

2019年CSP-S第二轮重现

未参加
状态
已结束
规则
IOI
题目
3
开始于
2023-10-11 11:45
结束于
2023-10-20 15:45
持续时间
220 小时
主持人
参赛人数
25