题目描述
建树+遍历树对比颜色,不一样就加一
import java.util.*;
public class Main {
public static List<List<Integer>> edges = new ArrayList();
public static int ans = 0;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNext()) {
int n = in.nextInt();
for ( int i = 0; i <= n; ++i ) {
edges.add(new ArrayList());
}
in.nextLine();
String line = in.nextLine();
String[] nums = line.split(" ");
for (int i = 0; i < n-1; i++) {
int a = Integer.parseInt(nums[i]);
edges.get(a).add(i+2);
}
int[] brr = new int[n+1];
for (int i = 1; i <= n; i++) {
brr[i] = in.nextInt();
// System.out.println(brr[i]);
}
//return ;
Queue<int[]> q = new ArrayDeque();
q.offer(new int[]{1,0});
while(!q.isEmpty()){
int[]t = q.poll();
int cur = t[0];
int color = t[1];
if (color != brr[cur]) {
ans++;
}
//System.out.println("cur:"+cur);
List<Integer>children = edges.get(cur);
for (int child:children){
int[]tmp =new int[2];
tmp[0] = child;
tmp[1] = brr[cur];
// System.out.println("child:"+child);
q.offer(tmp);
}
//System.out.println(ans);
//return;
}
System.out.println(ans);
}
}
// public static void dfs(int cur,int color,int[]brr) {
// List<Integer> children = edges.get(cur);
// if (brr[cur] == color) {
// for( int child:children) {
// dfs(child,color,brr);
// }
// }else {
// ans++;
// for(int child:children){
// dfs(child,brr[cur],brr);
// }
// }
// }
}