题目描述

Farmer John 对之前解决平衡括号串问题的经历非常着迷，现在 Farmer John 想请你帮忙解决最后一个问题。

FJ 的农场是由 $N$ 个牧场组成的一棵大树，每个牧场都被他标记为了 ( 或 )。例如：

'('--'('--')'--'('--')'
 |         |
')'       ')'--'('--'(' 
 |              |
')'            '('--')'--')'--')'--'('

由于农场是一棵树，这意味着某些牧场之间通过路径连接，任意两个牧场之间有且只有一条唯一的路径。

FJ 相信，这些路径中的某些路径代表了一串平衡括号字符串。具体来说，他想知道在所有由树中路径表示的平衡字符串中，最大嵌套深度是多少。

一个平衡括号字符串的嵌套深度是指该字符串所有前缀中左括号比右括号多出的最大数目。

例如，字符串 ()()() 的嵌套深度为 $1$，而字符串 ((()))() 的嵌套深度为 $3$。我们可以通过计算每个前缀中左括号的超出数量来清楚地看到这一点：

((()))()
12321010

对于上面的示例，拥有最大嵌套深度的字符串是 ((()))，其深度为 $3$，可以通过如下的从 $A$ 到 $B$ 的路径获得：

'('--'('--')'--'('--')' 
|         | 
')'       ')'--'('--'(' < A 
|              | 
')'            '('--')'--')'--')'--'(' 
^C                            ^B 

注意：最深的字符串与最长的平衡字符串不同。例如，从 $A$ 到 $C$ 的路径 (())(()) 的长度为 $8$，然而，它不是拥有最大嵌套深度的字符串。

你的任务是，输出树中拥有最大嵌套深度的路径的嵌套深度。

输入格式

第 $1$ 行包含一个整数 $N$，表示树中节点的数量。

第 $2\sim N$ 行，第 $i+1$ 行包含一个整数 $p_{i+1}$（$1\le p_{i+1}\le i$），表示节点 $i+1$ 和节点 $p_{i+1}$ 之间有一条边。

第 $N+1\sim 2N$ 行：第 $N+i$ 行包含一个字符 ( 或 )，表示节点 $i$ 对应的标记。

输出格式

输出包含一行。输出一个整数，表示树中拥有最大嵌套深度的路径的嵌套深度。

15 
1 
2 
1 
4 
4 
6 
7 
5 
9 
9 
11 
12 
13 
14 
( 
) 
) 
( 
) 
) 
( 
) 
( 
( 
( 
) 
) 
) 
( 

3 

提示

【样例说明】

题目样例中的树形图如下所示：

1'('--4'('--6')'--7'('--8')' 
|     |
2')'  5')'--9'('--10'(' 
|           |
3')'       11'('--12')'--13')'--14')'--15'(' 

【数据范围】

对于 $100\%$ 的数据，$1\le N\le40000$。

翻译 & 格式修复 by FakzianQwQ。