华为

树的最大路径和

题目描述：计算树节点间最大路径和；

输入：

第一行为除了根节点的节点数；

接下来n行每一列分别为：节点id，父节点id，节点间的值val；

输出：最大路径和；

案例：

7
0 1 8
1 -1 -2
2 1 9
4 0 -2
5 4 3
3 0 -3
6 2 -3
输出：9

public class T2 {
    static Map<Integer, ArrayList<Integer>> graph = new HashMap<>();
    static int[] value;
    static int res = Integer.MIN_VALUE;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for(int i=0;i<n;i++){
            graph.put(i,new ArrayList<Integer>());
        }
        value = new int[n];
        for(int i=0;i<n;i++){
            int id = sc.nextInt();
            int fa = sc.nextInt();
            if(fa != -1){
                graph.get(fa).add(id);
            }
            value[id] = sc.nextInt();
        }
        for(int i=0;i<n;i++){
            dfs(i,0);
        }
        System.out.println(res);
    }
    static void dfs(int i, int sum){
        sum += value[i];
        res = Math.max(res,sum);
        for(int j:graph.get(i)){
            dfs(j,sum);
        }
    }
}