dfs+memorize
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```\nclass Solution {\n    int result=0;\n    public int maximalPathQuality(int[] values, int[][] edges, int maxTime) {\n       List<Node>[]connections=new ArrayList[values.length];\n       for(int i=0;i<values.length;i++)\n            connections[i]=new ArrayList<>();\n        for(int []edge:edges)\n        {\n            connections[edge[0]].add(new Node(edge[1],edge[2]));\n            connections[edge[1]].add(new Node(edge[0],edge[2]));\n        }\n        dfs(new Edg(0,0,0),connections,maxTime, new boolean[values.length][values.length],values);\n        return result;\n    }\n\n    void dfs(Edg edg, List<Node>[]connections,int maxTime,boolean [][]visited,int []values)\n    {\n        if(edg.sumTime>maxTime)\n            return;\n        edg.sum+=values[edg.num];\n        if(edg.num==0)\n            result=Math.max(result,edg.sum);\n        int temp=values[edg.num];\n        values[edg.num]=0;\n        for(Node nod:connections[edg.num])\n        {\n           if(visited[edg.num][nod.num])\n                continue;\n            visited[edg.num][nod.num]=true;\n            dfs(new Edg(nod.num,edg.sumTime+nod.time,edg.sum),connections,maxTime,visited,values);\n            visited[edg.num][nod.num]=false; \n        }\n        values[edg.num]=temp;   \n    }\n\n}\n\nclass Node{\n    int num;\n    int time;\n    public Node(int n, int t){num=n;time=t;}\n}\nclass Edg{\n    int num;\n    int sumTime;\n    int sum;\n    public Edg(int n, int t, int s){num=n; sumTime=t; sum=s;}\n    \n}\n```
['Java']