最长路径

public class Solution {

    private long maxRes = 0;
    private ArrayList<ArrayList<Node>> nodes;

    /**
     * 返回最终结果
     *
     * @param n int整型 城市数量
     * @param u int整型一维数组
     * @param v int整型一维数组
     * @param w int整型一维数组
     * @return long长整型
     */
    public long solve(int n, int[] u, int[] v, int[] w) {
        // write code here
        nodes = new ArrayList<>(n + 1);
        for(int i = 0; i <= n; i++) {
            nodes.add(new ArrayList<>());
        }
        for(int i = 0; i < u.length; i++) {
            nodes.get(u[i]).add(new Node(v[i], w[i]));
            nodes.get(v[i]).add(new Node(u[i], w[i]));
        }
        dfs(1, -1);
        return maxRes;
    }

    long dfs(int toIndex, int fromIndex) {
        long subMax = 0;
        for(Node node : nodes.get(toIndex)) {
            if (node.index != fromIndex) {
                long curSubNum = dfs(node.index, toIndex) + node.weight;
                maxRes = Math.max(maxRes, subMax + curSubNum);
                subMax = Math.max(subMax, curSubNum);
            }
        }
        return subMax;
    }

    static class Node {
        int index;
        int weight;

        public Node(int index, int weight) {
            this.index = index;
            this.weight = weight;
        }
    }
｝

import java.util.*;


public class Solution {
    long  maxLength = 0;
    /**
     * 返回最终结果
     * @param n int整型 城市数量
     * @param u int整型一维数组 
     * @param v int整型一维数组 
     * @param w int整型一维数组 
     * @return long长整型
     */
    public long solve (int n, int[] u, int[] v, int[] w) {
        // write code here
        //可以使用dfs
        //首先存储每个房子能够连接哪些房子，并且长度是多少
        Map<Integer,Map<Integer,Integer>> map = new HashMap<>();
        for(int i = 0;i<n-1;i++){
            if(!map.containsKey(u[i])){
                map.put(u[i],new HashMap<>());
            }
            map.get(u[i]).put(v[i],w[i]);
            if(!map.containsKey(v[i])){
                map.put(v[i],new HashMap<>());
            }
            map.get(v[i]).put(u[i],w[i]);
        }
        //此时可以遍历进行dfs
        for(int i = 1;i<=n;i++){
            //这里可以优化，最长路径肯定是从叶子节点开始的
            if(map.get(i).size()==1){
                getLong(map,new HashSet<Integer>(),i,0);
            }
        }
        return maxLength;
    }
    public void getLong(Map<Integer,Map<Integer,Integer>> map,Set<Integer> usedSet,int start,int maxLen){
        maxLength = Math.max(maxLength,maxLen);
        for(int i : map.get(start).keySet()){
            if(!usedSet.contains(i)){
                maxLen += map.get(start).get(i);
                usedSet.add(start);
                getLong(map,usedSet,i,maxLen);
                usedSet.remove(start);
                maxLen -= map.get(start).get(i);
            }
        }
    }
}