Java DFS Solution
Classic DFS. Since we can visit a node many times, it is necessary to keep its frequency in a hashmap. The code should explains itself.\n\nclass Solution {\n   
Classic DFS. Since we can visit a node many times, it is necessary to keep its frequency in a hashmap. The code should explains itself.\n```\nclass Solution {\n    Map<Integer, List<Pair<Integer, Integer>>> map = new HashMap<>(); // source, dest, time\n    int max = 0;\n    int[] values;\n    \n    public int maximalPathQuality(int[] values, int[][] edges, int maxTime) {\n        this.values = values;\n        \n        // construct map\n        for (int[] edge : edges) {\n            int v1 = edge[0];\n            int v2 = edge[1];\n            int time = edge[2];\n            \n            insert(v1, new Pair(v2, time));\n            insert(v2, new Pair(v1, time));\n        }\n        \n        // use hashmap to record the path\n        Map<Integer, Integer> freq = new HashMap<>();\n        freq.put(0, 1);\n        dfs(0, maxTime, 0, freq);\n        \n        return max;\n    }\n    \n    private void insert(int key, Pair<Integer, Integer> pair) {\n        if (!map.containsKey(key)) {\n            map.put(key, new ArrayList<>());\n        }\n        map.get(key).add(pair);\n    }\n    \n    private void dfs(int root, int maxTime, int currTime, Map<Integer, Integer> freq) {\n        if (currTime > maxTime) {\n            return;\n        }\n        if (root == 0) {\n            max = Math.max(max, computeValues(freq));\n        }\n        \n        List<Pair<Integer, Integer>> neighbors = map.get(root);\n            \n        if (neighbors != null) {\n            for (Pair<Integer, Integer> pair : neighbors) {\n                int n_idx = pair.getKey();\n                int n_time = pair.getValue();\n                \n                freq.put(n_idx, freq.getOrDefault(n_idx, 0) + 1);\n                dfs(n_idx, maxTime, currTime + n_time, freq);\n                freq.put(n_idx, freq.get(n_idx) - 1);\n                \n                // remember to remove the node if its frequency is 0\n                if (freq.get(n_idx) == 0) {\n                    freq.remove(n_idx);\n                }\n            }\n        }\n    }\n    \n    private int computeValues(Map<Integer, Integer> freq) {\n        int sum = 0;\n        \n        for (int idx : freq.keySet()) {\n            sum += values[idx];\n        }\n        \n        return sum;\n    }\n}\n```
[]