猿辅导笔试第二题（Java版）-小猿抽奖
第二题参考大佬发的帖子，自己整理成了Java版，如有不对还请指正~
HashMap + DFS 进行求解
用Hashmap存储边之间的关系，然后依据节点之间的关系进行查找最大值。
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);
}
}
