35187번 - 회귀자 니아와 그린나무 게임

실험체 겸 지휘관, 트레이너, 선생, 관리자, 방랑자, 마스터, 사령관, 모험가, 헌터, 개척자, 교주이자 회귀자인 니아는 데비와 그린 나무 게임을 하려고 한다.

그린 나무 게임은 정점의 수가 $N$개인 트리에서 진행한다. 트리의 각 정점은 초록색, 빨강색, 파랑색 중 한 색깔로 칠해져 있다. 또한, 트리의 $1$번 정점이자 루트 정점은 초록색이다.

게임은 둘이 돌아가며 각자 턴에 데비는 부모 정점이 초록색인 파랑색 정점 하나를 초록색 정점으로 바꾸며, 니아는 부모 정점이 초록색인 빨강색 정점 하나를 초록색 정점으로 바꾼다. 이때 자신의 차례에 행동을 할 수 없는 플레이어가 패배한다.

게임은 언제나 데비가 먼저 시작한다. 니아는 이 게임을 꼭 이기고 싶기 때문에 게임 중간에 회귀를 하여 승리를 하려고 한다. 니아가 영원하지 않은 회귀를 하면 게임판의 상태는 그대로 유지된 채, 그 상황에서 처음부터 데비가 시작하는 시점으로 돌아간다. 회귀는 어느 시점에나 원하는 만큼 할 수 있다.

니아는 최대한 적은 횟수만큼 회귀하여 게임에서 승리하고자 한다. 이때, 니아가 승리하기 위해서 최악의 경우 겪어야 할 회귀 횟수를 구하여라.

첫 번째 줄에 트리의 정점의 개수 $N$이 주어진다.

두 번째 줄에는 $N-1$개의 정수 $P_2$, $P_3$, $\cdots$, $P_N$이 공백으로 구분되어 주어진다. $P_i$는 트리에서 $i$번 정점의 부모 정점의 번호를 의미한다.

세 번째 줄에는 $N$개의 문자 $C_1$, $C_2$, $\cdots$, $C_N$이 공백으로 구분되어 주어진다. $C_i$는 R, G 또는 B이며, 이는 각각 $i$번 정점의 색깔이 빨강색, 초록색, 또는 파란색이라는 것을 의미한다.

니아가 승리하기 위해서 최악의 경우 겪어야 할 회귀 횟수를 구하여라.

• 주어지는 모든 수는 정수이다.
• $2\le N\le 1\, 000\, 000$
• $1\le P_i<i$ ($2\le i\le N$)
• $C_i$ 는 R, G, B 중 하나이다. ($1\le i\le N$)
• $C_1$ 은 G 이다.