#CSPS2019B. 括号树 (Bracket Tree)

括号树 (Bracket Tree)

Description

In this question, we define a bracket string that meets the following requirements as a "legal bracket string":

  1. () is a "legal bracket string".
  2. If A is a "legal bracket string", then (A) is also a "legal bracket string".
  3. If A and B are both "legal bracket strings", then AB is also a "legal bracket string".

The definition of substring and different substring in this question is as follows:

  1. We use S(l,r)S(l,r) (1lrS1\le l \le r \le |S|, which S|S| is the length of SS) to represent a substring of SS. It means a string consisting of any consecutive characters from ll to rr in SS.
  2. Two substrings of S are considered different if and only if their positions in S are different, (i.e. ll is different or rr is different).

Little Q has a rooted tree which rooted at node 11 and the number of nodes is nn. Except for node 11, the parent node of node u(2un)u(2\le u\le n) is fu(1fu<u)f_u(1\le f_u < u).

Little Q finds that there is exactly one bracket on each node of this tree, which may be ( or ). He defines sis_i as a string composed of brackets on the simple path from the root node to the node ii and arranged in sequence according to the sequence of the nodes.

Obviously sis_i is a bracket string, but it may not be a "legal bracket string". So now Little Q wants to find out how many different substrings of sis_i are "legal bracket strings" for all i(1in)i(1\le i\le n).

Assuming that there are kik_i different substrings of sis_i as "legal bracket strings", you only need to tell Little Q the bitwise XOR of all i×kii\times k_i, which is:

(1×k1)xor(2×k2)xor(3×k3)xorxor(n×kn)(1\times k_1)\operatorname{xor}(2\times k_2)\operatorname{xor}(3\times k_3)\operatorname{xor}\cdots\operatorname{xor}(n\times k_n)

Among them, xor\text{xor} is bitwise XOR operation.

Input Format

The first line contains an integer nn, which represents the number of nodes in the tree.

The second line contains an bracket string of length nn, which the ii-th bracket represents the bracket on the ii-th node.

The third line contains n1n-1 integer. The ii-th integer represents the father of (i+1)(i+1)-th node fi+1f_{i+1}.

Output Format

Print one integer in a single line, which is the answer.

5
(()()
1 1 2 2
6

The shape of the tree is as follows:

  • The brackets on the simple path from the root to node 11 are arranged in order to form a string of (, and the number of substrings that are "legal bracket strings" is 00.
  • The brackets on the simple path from the root to node 22 are arranged in order to form a string of ((, and the number of substrings that are "legal bracket strings" is 00.
  • The brackets on the simple path from the root to node 33 are arranged in order to form a string of (), and the number of substrings that are "legal bracket strings" is 11.
  • The brackets on the simple path from the root to node 44 are arranged in order to form a string of (((, and the number of substrings that are "legal bracket strings" is 00.
  • The brackets on the simple path from the root to node 55 are arranged in order to form a string of ((), and the number of substrings that are "legal bracket strings" is 11.

Sample 2

See attached files brackets2.in and brackets2.ans.

Sample 3

See attached files brackets3.in and brackets3.ans.

Constraints

# nn\le Special Properties
121\sim 2 88 fi=i1f_i=i-1
343\sim4 200200
575\sim 7 2×1032\times 10^3
8108\sim 10 None
111411\sim 14 10510^5 fi=i1f_i=i-1
151615\sim 16 None
172017\sim 20 5×1055\times 10^5