레이팅 미적용지금까지의 균형 잡힌 괄호 경험에 매료된 농부 존(Farmer John)은 마지막 문제 하나를 풀 수 있게 도와줄 수 있는지 궁금해한다. 알고 보니 FJ의 농장은 N개 (1 <= N <= 40,000)의 목초지로 이루어진 거대한 트리 모양이며, 존은 각 목초지에 ( 또는 ) 라벨을 붙여 두었다.
농장이 트리이므로, 특정 목초지 쌍들이 통로로 연결되어 있어 임의의 목초지 쌍 사이에 유일한 경로가 존재한다는 뜻임을 기억하자. FJ는 이 경로들 중 일부가 균형 잡힌 괄호 문자열을 나타낸다고 믿는다. 특히 존은 트리의 경로가 나타내는 모든 균형 잡힌 문자열 중에서 찾을 수 있는 최대 중첩 깊이를 알고 싶어 한다. 균형 잡힌 괄호 문자열의 중첩 깊이란, 문자열의 모든 접두사에 대해 접두사 안에서 (가 )보다 많은 초과 개수의 최댓값이다. 예를 들어 문자열 ()()()의 중첩 깊이는 1이지만, 문자열 ((()))()의 중첩 깊이는 3이다.
당신의 임무는 트리에서 가장 깊은 균형 잡힌 경로의 중첩 깊이를 출력하는 것이다.
첫째 줄: 트리의 노드 수를 나타내는 정수 N.
둘째 줄부터 N번째 줄까지: i+1번째 줄에 정수 p_(i+1) (1 <= p_(i+1) <= i)이 주어지며, 트리에서 노드 i+1과 p_{i+1} 사이에 간선이 있음을 나타낸다.
N+1번째 줄부터 2N번째 줄까지: N+i번째 줄에 노드 i의 라벨인 ( 또는 )가 주어진다.
균형 잡힌 경로의 최대 중첩 깊이를 나타내는 정수 하나.
btree.in · 출력을 쓸 파일 btree.out15
1
2
1
4
4
6
7
5
9
9
11
12
13
14
(
)
)
(
)
)
(
)
(
(
(
)
)
)
(3riseoj 작성
출처 올림피아드 > USACO > 2012-2013 > November > Gold