Simple Java Backtracking Solution
\nclass Solution {\n    int res = 0;\n\n    public int maximalPathQuality(int[] values, int[][] edges, int maxTime) {\n        Map<Integer, Map<Integer, Integer
```\nclass Solution {\n    int res = 0;\n\n    public int maximalPathQuality(int[] values, int[][] edges, int maxTime) {\n        Map<Integer, Map<Integer, Integer>> map = new HashMap<>();\n        int n = values.length;\n        for (int i = 0; i < n; i++) map.put(i, new HashMap<>());\n        for (int[] edge : edges) {\n            map.get(edge[0]).put(edge[1], edge[2]);\n            map.get(edge[1]).put(edge[0], edge[2]);\n        }\n        Map<Integer, Integer> visited = new HashMap<Integer, Integer>();\n        visited.put(0, 1);\n        dfs(0, maxTime, values[0], visited, values, map);\n        return res;\n    }\n\n    public void dfs(int cur, int time, int value, Map<Integer, Integer> visited, int[] values, Map<Integer, Map<Integer, Integer>> map) {\n        if (cur == 0) {\n            res = Math.max(res, value);\n        }\n        for (Map.Entry<Integer, Integer> entry : map.get(cur).entrySet()) {\n            if (time < entry.getValue()) continue;\n            if (!visited.containsKey(entry.getKey())) value += values[entry.getKey()];\n            visited.put(entry.getKey(), visited.getOrDefault(entry.getKey(), 0) + 1);\n            dfs(entry.getKey(), time - entry.getValue(), value, visited, values, map);\n            visited.put(entry.getKey(), visited.getOrDefault(entry.getKey(), 0) - 1);\n            if (visited.get(entry.getKey()) == 0) {\n                visited.remove(entry.getKey());\n                value -= values[entry.getKey()];\n            }\n        }\n    }\n}\n```
['Backtracking', 'Graph', 'Java']