Java DFS - key is to flip the newVisit
IntuitionApproachComplexity
Time complexity:

Space complexity:
Code
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->

# Approach
<!-- Describe your approach to solving the problem. -->

# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```java []
class Solution {
    private int ans;
    private List<int[]>[] graph;
    private int[] values;

    public int maximalPathQuality(int[] values, int[][] E, int maxTime) {
        int n = values.length;
        this.values = values;
        // Build the graph (undirected)
        graph = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int[] edge : E) {
            int u = edge[0], v = edge[1], w = edge[2];
            graph[u].add(new int[]{v, w});
            graph[v].add(new int[]{u, w});
        }
        ans = 0;
        // visited[i] is true if node i has been visited in the current path
        boolean[] visited = new boolean[n];
        visited[0] = true; // Start at node 0
        dfs(0, values[0], maxTime, visited);
        return ans;
    }

    private void dfs(int node, int gain, int timeLeft, boolean[] visited) {
        // Whenever we return to node 0, update our answer
        if (node == 0) {
            ans = Math.max(ans, gain);
        }
        // Explore all neighbors of the current node
        for (int[] edge : graph[node]) {
            int neib = edge[0], cost = edge[1];
            if (cost <= timeLeft) {
                boolean newVisit = false;
                // Only add the neighbor's value if it's the first time visiting it
                if (!visited[neib]) {
                    newVisit = true;
                    visited[neib] = true;
                }
                dfs(neib, gain + (newVisit ? values[neib] : 0), timeLeft - cost, visited);
                // Backtrack: if we marked neib as newly visited in this call, unmark it
                if (newVisit) {
                    visited[neib] = false;
                }
            }
        }
    }
}

```
['Java']