括号树

【题目背景】

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

1.0是合法括号串。

2.如果A是合法括号串，则(A)是合法括号串。

3.如果A, B是合法括号串，则AB是合法括号串。

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

1.字符串S的子串是S中连续的任意个字符组成的字符串。S的子串可用起始位置l与终止位置r来表示，记为S(l,r)(1≤l≤r≤|S|,|S|表示S的长度)。

2.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所有ixki的异或和，即：

(1 x k1) xor (2 x k2) xor (3 x k3)xor .…xor (n x kn)其中xor是位异或运算。

【输入格式】

从文件brackets.in中读入数据。

第一行一个整数n，表示树的大小。

第二行一个长为n的由'('与')'组成的括号串，第i个括号表示i号结点上的括号。 

第三行包含n-1个整数，第i(1≤i<n)个整数表示i+1号结点的父亲编号fi+1。

【输出格式】

输出到文件brackets.out中。

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

【样例1输入】

5

（（）（）

1 1 2 2

【样例1输出】

6

【样例1解释】

树的形态如下图:

将根到1号结点的简单路径上的括号，按经过顺序排列所组成的字符串为（，子串 是合法括号串的个数为0。

将根到2号结点的简单路径上的括号，按经过顺序排列所组成的字符串为（（，子 串是合法括号串的个数为0。

将根到3号结点的简单路径上的括号，按经过顺序排列所组成的字符串为（），子 串是合法括号串的个数为1。

将根到4号结点的简单路径上的括号，按经过顺序排列所组成的字符串为（（（，子 串是合法括号串的个数为0。

将根到5号结点的简单路径上的括号，按经过顺序排列所组成的字符串为（（），子 串是合法括号串的个数为1。

【数据范围】