携程java后端笔试8.30 第三题

这里虽然是树，但其实要用图来做
思路：
图上的任意一个节点都可做树根。
对全图颜色做hash计数。
设置访问状态数组。

随意选择一个节点做树根进行深搜。
对于当前节点，记录为访问过的状态。
将当前节点做树根，做后续遍历，返回每个子树统计的color的rgb计数，并累计，最后加上树根的颜色。
得到以当前节点为树根的树的颜色hash，看是否rgb都包含，并用全图颜色hash计数和其相减，可得到另一子图的颜色计数，判断合法。
最后返回子树的颜色hash
以此类推，只需要深搜一次，应该不会超时
事后想到的，不晓得能过多少用例。
java代码如下

import java.util.*;
public class Main {
    public static boolean[] visit;
    public static Map> linjiebiao;
    public static int[] colorhash;
    public  static int  ans=0;
    public  static String colors;
    public static void main(String[] args) {
        Scanner s=new Scanner(System.in);
        int n=s.nextInt();
        visit=new boolean[n];
        colors=s.next();
        //color hash
        colorhash=new int[3];
        for (char ch:colors.toCharArray()) {
            if(ch=='r')colorhash[0]++;
            else if(ch=='g')colorhash[1]++;
            else if(ch=='b')colorhash[2]++;
        }
        //构建图
        linjiebiao=new HashMap();
        int[][] edges=new int[n-1][2];
        for(int i=0;i<n-1;i++){
            int a,b;
            a=s.nextInt()-1;
            b=s.nextInt()-1;
            edges[i][0]=a;
            edges[i][1]=b;
            List list;
            if(linjiebiao.containsKey(a)){
                list=linjiebiao.get(a);
            }else {
                list=new ArrayList();
            }
            list.add(b);
            linjiebiao.put(a,list);
            if(linjiebiao.containsKey(b)){
                list=linjiebiao.get(b);
            }else {
                list=new ArrayList();
            }
            list.add(a);
            linjiebiao.put(b,list);
        }
        //随意选一个节点当树根
        dfs(3);
        System.out.println(ans);
    }
    public static int[] dfs(int root){
        //后续遍历
        visit[root]=true;
        int[] roothash=new int[3];
        List child=linjiebiao.get(root);
        for(int nei:child){
            if(!visit[nei]){
                int[] thash=dfs(nei);
                for(int i=0;i<3;i++)roothash[i]+=thash[i];
            }
        }
        char ch=colors.charAt(root);
        if(ch=='r')roothash[0]++;
        else if(ch=='g')roothash[1]++;
        else if(ch=='b')roothash[2]++;
        //后续遍历
        int co3=0;
        boolean flag=false;
        for(int i=0;i<3;i++){
            if(roothash[i]==0){
                flag=true;
                break;
            }
            if(colorhash[i]-roothash[i]==0){
                flag=true;
                break;
            }
        }
        if(!flag&&root!=3)ans++;//注意，总树根这里相当于没有断边，可以排除一下这种情况，但其实这种情况由于另一子图为空，肯定不满足情况。这里写，便于理解
        System.out.print("root:"+root+"   :");
        for (int i = 0; i < 3; i++) {
            System.out.print(" "+roothash[i]);
        }
        System.out.println();
        return roothash;
    }
}