[数据结构与算法]2022.3.11-----leetcode.2049

 //超时了，哎。。。
static int num;
    public static int countHighestScoreNodes(int[] parents) {
        int n=parents.length;
        List<Integer>[] kids=new List[n];//存储节点的子节点
        for (int i = 1; i <n ; i++) {
           if(kids[parents[i]]==null)
               kids[parents[i]]=new ArrayList<>();
            kids[parents[i]].add(i);
        }
        long max=0;//最大分数
        int ans=0;//最大分数数量
        for (int i = 0; i < n; i++) {
            //初始化
            num=0;
            int left=0;
            int right=0;
            //求左子树与右子树节点
            if(kids[i]!=null){
                if(kids[i].size()>=1)
                    left=dfs(kids[i].get(0),kids);
                if(kids[i].size()==2){
                    num=0;
                    right=dfs(kids[i].get(1),kids);
                }
            }
            //如果为0记为1
            int rest=(n-left-right-1)==0?1:n-left-right-1;
            left=left==0?1:left;
            right=right==0?1:right;
            long score= (long) left *right*rest;//分数
            //更新答案
            if(max<score){
                max=score;
                ans=1;
            }else if(max==score) ans++;
        }
        return ans;
    }
    public static int dfs(int node,List<Integer>[] kids){
        if(kids[node]!=null){
            for (int i = 0; i < kids[node].size(); i++) {
                dfs(kids[node].get(i),kids);
            }
        }
        num++;
        return num;
    }