Maximum Path Quality of a Graph
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```java []\nimport java.util.*;\n\nclass Solution {\n    private int maxQuality = 0;\n\n    public int maximalPathQuality(int[] values, int[][] edges, int maxTime) {\n        // Step 1: Build the graph\n        Map<Integer, List<int[]>> graph = new HashMap<>();\n        for (int[] edge : edges) {\n            graph.computeIfAbsent(edge[0], k -> new ArrayList<>()).add(new int[]{edge[1], edge[2]});\n            graph.computeIfAbsent(edge[1], k -> new ArrayList<>()).add(new int[]{edge[0], edge[2]});\n        }\n\n        // Step 2: Initialize visited array to track how many times we visited each node\n        int[] visited = new int[values.length];\n\n        // Step 3: Start DFS from node 0 with time 0 and quality = values[0] (since we start at node 0)\n        dfs(graph, values, visited, 0, 0, values[0], maxTime);\n\n        return maxQuality;\n    }\n\n    private void dfs(Map<Integer, List<int[]>> graph, int[] values, int[] visited, int node, int time, int quality, int maxTime) {\n        // Step 4: If we are back at node 0, update the maximum quality\n        if (node == 0) {\n            maxQuality = Math.max(maxQuality, quality);\n        }\n\n        // Mark this node as visited\n        visited[node]++;\n\n        // Step 5: Explore all neighboring nodes\n        for (int[] neighbor : graph.getOrDefault(node, new ArrayList<>())) {\n            int nextNode = neighbor[0];\n            int travelTime = neighbor[1];\n\n            // If the travel time exceeds the maximum allowed time, skip this path\n            if (time + travelTime > maxTime) continue;\n\n            // Calculate the new quality if it\'s the first time visiting this node\n            int newQuality = quality;\n            if (visited[nextNode] == 0) {\n                newQuality += values[nextNode];\n            }\n\n            // Continue DFS from the next node\n            dfs(graph, values, visited, nextNode, time + travelTime, newQuality, maxTime);\n        }\n\n        // Backtrack: unmark this node as visited\n        visited[node]--;\n    }\n}\n\n```
['Java']