Easy CPP Solution Beats 90% users
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```cpp []\nclass Solution {\npublic:\n    vector<vector<pair<int,int>>> adj;\n    vector<int> best;\n    void dfs(int rt,int time,int ans,int k,vector<int>& values,vector<int>& vis){\n        int f=0;\n        if(vis[rt]==0) f=1;\n        int has = vis[rt]==0 ? values[rt] : 0;\n        vis[rt] = 1;\n        \n        for(auto v:adj[rt]){\n            int ch = v.first;\n            int t = v.second;\n            if(time+t<=k){\n                dfs(ch,time+t,ans+has,k,values,vis);\n            }\n        }\n        if(f)vis[rt] = 0;\n        best[rt] = max(best[rt],ans+has);\n    }\n    int maximalPathQuality(vector<int>& values, vector<vector<int>>& edges, int maxTime) {\n        int n=values.size();\n        adj = vector<vector<pair<int,int>>> (n);\n        best = vector<int>(n,0);\n        for(auto e:edges){\n            int u=e[0];\n            int v=e[1];\n            int t=e[2];\n            adj[u].push_back({v,t});\n            adj[v].push_back({u,t});\n        }\n        vector<int> vis(n,0);\n        dfs(0,0,0,maxTime,values,vis);\n        return best[0];\n    }\n};\n```
['C++']