C++ || DFS || Easy to understand
\nclass Solution {\npublic:\n    int rec(vector<int>& values, vector<vector<pair<int,int>>>& vec, int maxt,int x)\n    {\n        int ans=INT_MIN;\n        if(x
```\nclass Solution {\npublic:\n    int rec(vector<int>& values, vector<vector<pair<int,int>>>& vec, int maxt,int x)\n    {\n        int ans=INT_MIN;\n        if(x==0)\n            ans=0;\n        for(int i=0;i<vec[x].size();i++)\n        {\n            int a=vec[x][i].first,b=vec[x][i].second;\n            if(b<=maxt)\n            {\n                int v=values[a];\n                values[a]=0;\n                int p=rec(values,vec,maxt-b,a);\n                if(p!=INT_MIN)\n                    ans=max(ans,p+v);\n                values[a]=v;\n            }\n        }\n        return ans;\n    }\n    int maximalPathQuality(vector<int>& values, vector<vector<int>>& edges, int maxt) {\n        int trav=0;\n        vector<vector<pair<int,int>>> vec(values.size()+5);\n        for(int i=0;i<edges.size();i++)\n        {\n            int a=edges[i][0],b=edges[i][1],c=edges[i][2];\n            vec[a].push_back({b,c});\n            vec[b].push_back({a,c});\n        }\n        int v=values[0];\n        values[0]=0;\n        return rec(values,vec,maxt,0)+v; \n    }\n};\n```
['Backtracking', 'Depth-First Search', 'C', 'C++']