4.21小红书笔试第二题

import java.lang.reflect.Array;
import java.util.*;
import  java.io.*;
public class Main 
{    
  static ArrayList<Integer>[] g;  
  static int tmp;  
  static char[] c;  
  static ArrayList<Integer> res = new ArrayList<>(); 
  public static void main(String[] args) { 
	Scanner sc = new Scanner(System.in);    
	int n = sc.nextInt();    
	int k = sc.nextInt();      
	String s = sc.next();         
	c = s.toCharArray();   
	g = new ArrayList[n+1];  
	for(int i = 1; i <= n; i++) {
	  g[i] = new ArrayList<>();  
	}        
	for(int i = 0; i < n - 1; i++) {   
	  int x = sc.nextInt();   
	  int y = sc.nextInt();   
	  g[x].add(y);     
	  g[y].add(x);   
	}       
	for(int i = 1; i <= n; i++) { 
	  if (c[i - 1] == 'R') {     
		tmp = 1;       
		dfs(i, -1);      
		if (tmp != 0) {  
		  res.add(tmp);    
		}           
	  }      
	}         
	Object[] o = res.toArray();  
	Arrays.sort(o);     
	int count = 0;   
	if(res.size() < k) {  
	  System.out.println(-1);    
	}        
	for(int i = res.size() - 1; i >= 0; i--) {  
	  count++;        
	  if(count == k) {     
		System.out.println(o[i]);      
		break;            
	  }       
	}  
  }   
  public static void dfs(int cur, int prev) { 
	c[cur - 1] = 'W';       
	for(int v: g[cur]) {     
	  if(v != prev) {    
		if(c[v-1] == 'R') {  
		  tmp++;         
		  dfs(v,cur);       
		}          
	  }       
	}  
  }
}

来不及做了开会+赶班车，第二个题都没a出来，记录一下、大概是一个求某一颜色的连通子集的点的个数，然后输出倒数第k个，可以用力扣岛屿数量的思路去做。

4 2

RRWR

1 2

2 3

3 4

1