dfs brute force
python\n\'\'\'\ndfs, brute force\nO(4^n), O(4^n)\n\'\'\'\nclass Solution:\n    def maximalPathQuality(self, values: List[int], edges: List[List[int]], maxTime: 
```python\n\'\'\'\ndfs, brute force\nO(4^n), O(4^n)\n\'\'\'\nclass Solution:\n    def maximalPathQuality(self, values: List[int], edges: List[List[int]], maxTime: int) -> int:\n        graph = collections.defaultdict(list)\n        for u, v, time in edges:\n            graph[u].append((v, time))\n            graph[v].append((u, time))\n        \n        max_quality = 0\n        visited = {0}\n        def dfs(node, visited, quality, time_left):\n            nonlocal max_quality\n            \n            if node == 0:\n                max_quality = max(max_quality, quality)\n            \n            for neighbor, time in graph[node]:\n                if time <= time_left:\n                    if neighbor in visited:\n                        dfs(neighbor, visited, quality, time_left - time)\n                    else:\n                        visited.add(neighbor)\n                        dfs(neighbor, visited, quality + values[neighbor], time_left - time)\n                        visited.remove(neighbor)\n        \n        dfs(0, visited, values[0], maxTime)\n        return max_quality\n```
['Depth-First Search']