猿辅导笔试第二题（Java版）-小猿抽奖

package YuanFuDao;

import java.util.*;

public class Main {

    public static int dfs(int rt, int ans,int[] val, HashMap<Integer,LinkedList<Integer>> map){
        int ret = val[rt];
        if (map.containsKey(rt)){
            LinkedList<Integer> list = map.get(rt);
            for (int v :
                    list) {
                ret = Math.max(ret, ret + dfs(v,ans,val,map));
            }
        }
        ans = Math.max(ans, ret);
        return ans;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] val = new int[N];
        int rt = -1;
        HashMap<Integer, LinkedList<Integer>> map = new HashMap<>();
        for (int i = 0; i < N; i++) {
            int fa;
            val[i] = sc.nextInt();
            fa = sc.nextInt();
            if (fa == 0){
                rt = i;
            }else {
                int res = fa - 2;
               if (map.containsKey(res)){
                   LinkedList<Integer> list = map.get(res);
                   list.add(i);
               }else {
                   LinkedList<Integer> list = new LinkedList<>();
                   list.add(i);
                   map.put(res,list);
               }

            }

        }

        int ans = Integer.MIN_VALUE;
        int dfs = dfs(rt, ans, val, map);
        System.out.println("Max: "+dfs);
    }
}