题目描述

$\red{Farmer John }$对他迄今为止对平衡括号的体验着迷，很好奇您是否可以帮助他解决最后一个问题。事实证明，$\red{FJ }$的农场是一棵有 $\red{N }$个牧场的巨树（$\red{1 <= N <= 40,000）}$，每个牧 场他都用 $\red{( }$或 $\red{) }$标记。例如：

'$\red{(}$'$\red{--}$'$\red{(}$'$\red{--}$'$\red{)}$'$\red{--}$'$\red{(}$'$\red{--}$'$\red{)}$'

$\red{| |}$

'$\red{)}$' '$\red{)}$'$\red{--}$'$\red{(}$'$\red{--}$'$\red{(}$'

$\red{| |}$

'$\red{)}$' '$\red{(}$'$\red{--}$'$\red{)}$'$\red{--}$'$\red{)}$'$\red{--}$'$\red{)}$'$\red{--}$'$\red{(}$'

回想一下，由于他的农场是一棵树，这意味着某些对牧场由走廊连接，因此在任何给定牧场之间都有一条独特的路径。$\red{FJ }$认为其中一些路径代表平衡的括号串。特别是，他想知道，在所有由通过树的路径表示的平衡字符串中，可以找到的最大嵌套深度是多少。平衡的括号字符串的嵌套深度是在字符串的所有前缀中，前缀中多余的 $\red{(}$'$\red{s }$数量的最大值。例如，字符串 $\red{()()() }$的嵌套深度为 $\red{1，}$但字符串 $\red{((()))() }$的嵌套深度为 $\red{3，}$如果我们为字符串的每个前缀计算多余的 $\red{()，}$我们可以清楚地看到：

$\red{((()))()}$

$\red{12321010}$

对于上面的示例农场，最深的字符串是 $\red{((()))，}$深度为 $\red{3，}$可以通过以下从 $\red{A }$到 $\red{B }$的路径获得：

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

请注意，这与最长的平衡字符串不同；例如 $\red{(())(())，}$从 $\red{A }$开始到 $\red{C }$结束，长度为 $\red{8}$。

你的任务是输出树中最深平衡路径的嵌套深度。

给出一棵树，每个结点上有一个括号。问在所有括号平衡的路径中，最大嵌套层数为多少。

输入格式

第 $\red{1 }$行：单个整数 $\red{N，}$树中的节点数。

第 $\red{2..N }$行：第 $\red{i+1 }$行：单个整数 $\red{p_(i+1) (1 <= p_(i+1) <= i)，}$表示节点 $\red{i+1 }$和 $\red{p \_ \{i+1 }$之间的边$\red{\} }$在树上。

$\red{Lines N+1..2N: Line N+i: }$要么 $\red{( }$要么 $\red{)，}$节点 $\red{i }$的标签。

输出格式

第 $\red{1 }$行：单个整数，给出平衡路径的最大嵌套深度。

样例

输入样例

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

输出样例

3

提示

这是问题描述中的示例，具有以下节点标签：

$\red{1}$'$\red{(}$'$\red{--4}$'$\red{(}$'$\red{--6}$'$\red{)}$'$\red{--7}$'$\red{(}$'$\red{--8}$'$\red{)}$'

$\red{| |}$

$\red{2}$'$\red{)}$' $\red{5}$'$\red{)}$'$\red{--9}$'$\red{(}$'$\red{--10}$'$\red{(}$'

$\red{| |}$

$\red{3}$'$\red{)}$' $\red{11}$'$\red{(}$'$\red{--12}$'$\red{)}$'$\red{--13}$'$\red{)}$'$\red{--14}$'$\red{)}$'$\red{--15}$'$\red{(}$'