4.8 美团第五题

import java.util.*;
import java.lang.Math.*;
public class Main {   
  static  int res;   
  static  int[] dp = new int[1005]; 
  static int[] r = new int[1005];
  static int[] gr = new int[1005]; 
  static int[] b = new int[1005];   
  static int R ;   
  static int G ;   
  static int B ;  
  static ArrayList<Integer>[] g = new ArrayList[1005];
  public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);   
	int n = sc.nextInt(); 
	for (int i = 1; i <= n; i++) {       
	  g[i] = new ArrayList<>(); 
	}      
	for (int i = 1; i < n; i++) {  
	  int x = sc.nextInt();     
	  g[x].add(i+1);   
	  g[i+1].add(x);     
	}     
	String c = sc.next();  
	for (int i = 0; i < c.length(); i++) {    
	  if(c.charAt(i) == 'G')           
		G++;          
	  if(c.charAt(i) == 'R')  
		R++;     
	  if(c.charAt(i) == 'B')    
		B++;       
	}       
	dfs(1,-1,c);    
	dfs2(1,-1);   
	System.out.println(res);
  }   
  public static void dfs(int cur, int prev,String c) { 
	if(c.charAt(cur-1) == 'G') gr[cur]++;
	if(c.charAt(cur-1) == 'R') r[cur]++;   
	if(c.charAt(cur-1) == 'B') b[cur]++;
	for(int v: g[cur]) {      
	  if(v == prev) {     
		continue;            
	  }            
	  dfs(v,cur,c);       
	  gr[cur] += gr[v];      
	  r[cur] += r[v];          
	  b[cur] += b[v];       
	}   
  }    
  public static void dfs2(int cur, int prev) {  
	if(R - r[cur] > 0 && G - gr[cur] > 0 && B - b[cur] > 0 && r[cur] > 0 && gr[cur] > 0 && b[cur] > 0)  {  
	  res++;     
	}        
	for(int v: g[cur]) {   
	  if(v == prev) {    
		continue;        
	  }           
	  dfs2(v,cur);
	}    
  }
}

题目描述：
有一棵 n 个节点的树，树上每个点都有红绿蓝三种颜色中的一种。定义一棵树是多彩的，当且仅当这棵树同时存在一个红色节点，一个蓝色节点和一个绿色节点。

保证最初这棵树是多彩的，现在要砍掉这棵树的某一条边，请问有多少种砍法，使得砍完之后形成的两棵树都是多彩的。



输入描述
第一行一个整数 n，表示节点个数。

第二行 n-1 个整数 p2, p3, ..., pn，pi 表示树上 i 和 pi 两点之间有一条边。保证给出的一定是一棵树。

第三行一个长度为 n 的字符串，第 i 个字符表示第 i 个节点的初始颜色。其中 R 表示红色，G 表示绿色，B 表示蓝色。保证字符串只由这三种大写字母构成。

对于全部数据，3≤n≤1e5。

输出描述
输出一行，一个正整数，表示答案。


样例输入
7
1 2 3 1 5 5
GBGRRBB
样例输出
1
*/