균형 잡힌 괄호 트리

문제

농부 John의 농장은 $N$개의 목초지($1 \le N \le 40{,}000$)로 이루어진 거대한 트리 모양이다. 각 목초지에는 ( 또는 ) 중 하나가 적혀 있다. 농장이 트리이므로, 임의의 두 목초지 사이에는 정확히 하나의 단순 경로가 존재한다.

어떤 경로를 한 방향으로 따라가며 목초지의 글자를 읽으면 괄호 문자열이 만들어진다. 이 중 일부는 균형 잡힌 문자열이다. 트리의 경로에서 읽어 낼 수 있는 모든 균형 잡힌 문자열 가운데, 가능한 가장 큰 중첩 깊이를 구하려고 한다.

균형 잡힌 괄호 문자열의 중첩 깊이란, 모든 접두사에 대해 그 접두사에서 (의 개수에서 )의 개수를 뺀 값의 최댓값이다. 예를 들어 ()()()의 중첩 깊이는 $1$이고, ((()))()의 중첩 깊이는 $3$이다. 각 글자 아래에 (의 누적 초과 개수를 적어 보면 분명하다:

((()))()
12321010

다음은 각 목초지에 글자를 표시한 예시 농장이다:

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

경로는 한 방향으로만 읽으므로, 같은 두 목초지를 반대 방향으로 지나면 뒤집힌 문자열이 된다(예: ()와 )(). 두 방향 모두 허용된다.

위 농장에서 가장 깊은 균형 문자열은 ((()))이며 중첩 깊이는 $3$이다. 이는 A에서 B로 가는 경로에서 얻어진다:

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

이는 가장 긴 균형 문자열과는 다르다. 예를 들어 A에서 C로 가는 (())(())는 길이가 $8$이지만 중첩 깊이는 더 작다.

트리에서 가장 깊은 균형 경로의 중첩 깊이를 출력하라. 균형 잡힌 문자열을 만드는 경로가 하나도 없으면 $0$을 출력하라.

입력

첫째 줄: 트리의 노드 수인 정수 $N$.
$2 \ldots N$번째 줄: $i + 1$번째 줄에는 정수 $p_{i+1}$($1 \le p_{i+1} \le i$)이 하나 주어지며, 이는 노드 $i + 1$과 노드 $p_{i+1}$ 사이의 간선을 뜻한다.
$N + 1 \ldots 2N$번째 줄: $N + i$번째 줄에는 ( 또는 )가 주어지며, 이는 노드 $i$의 글자이다.

출력

정수 하나: 트리의 모든 균형 경로 중 최대 중첩 깊이. 균형 경로가 없으면 $0$.

힌트

이는 문제 설명에 나온 농장이며, 노드 번호를 함께 표시하면 다음과 같다:

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

가장 깊은 균형 경로는 $10 \to 9 \to 11 \to 12 \to 13 \to 14$이며, ((()))를 이루고 중첩 깊이는 $3$이다.