[Codeforces Round #790 (Div. 4)] G. White-Black Balanced Subtrees

---

https://codeforces.com/contest/1676/status/page/3?order=BY_JUDGED_DESC 

Status - Codeforces Round #790 (Div. 4) - Codeforces

By * Dukkha, contest

 

※. 각 노드의 색이 주어졌을 때 어떤 노드의 색을 포함한 하위 트리의 색(검정색, 하얀색) 개수가 같은 노드의 수를 구하는 문제

 

※. 최상위 노드는 1로 고정이고, (The second line ...  (1≤ai<i) — the parents of the vertices 2,…,n2,…,n)

상위 노드 먼저 주어진다.(index가 높은 수는 무조건 하위노드다.)

 

1. 배열을 생성 후 arr[index] = value - 1 (부모 노드)를 저장해준다.2. 문자열을 byte배열로 받고 getBytes()를 써준다. ( == charAt)3. 새로운 배열(kk)을 생성하고 각 노드마다 검은색이면 -1, 하얀색이면 1을 저장해준다.4. 위의 규칙에 따라 index가 높은 노드들은 무조건 하위노드이기 때문에 뒤에서 부터 index의 부모 노드들에 자기 자신의(kk)배열을 더해준다. (하얀색과 검은색의 수가 같다면 0, 검은색이 많다면 -1 < ...)5. kk 배열을 다시 탐색해 0인것(하얀색과 검은색의 수가 같은것) 이 있다면 결과값을 추가해준다.

 

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
 	public static void main(String arg[]) throws IOException {
 		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 		StringBuilder sb = new StringBuilder();
 		int T = Integer.parseInt(br.readLine());
 		while(T --> 0) {
 			int n = Integer.parseInt(br.readLine());
 			int[] arr = new int[n];
 			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
 			for(int i = 1; i < n; i++) {
 				arr[i] = Integer.parseInt(st.nextToken()) - 1;
 			}
 			byte[] cc = br.readLine().getBytes();
 			int[] kk = new int[n];
 			for(int i = 0; i < n; i++) {
 				kk[i] = cc[i] == 'B' ? 1 : -1;
 			}
 			for(int i = n-1; i > 0; i--) {
 				kk[arr[i]] += kk[i];
 			}
 			int ans = 0;
 			for(int i = 0; i < n; i++) {
 				if(kk[i] == 0)
 					ans++;
 			}
 			sb.append(ans).append('\n');
 		}
 		System.out.println(sb);
 	}
}