Max Simplified Backtracking Cpp 👨‍💻
Why Backtracking ?\nBecause we got at most 4 children of a node and no need of worrying out infinite recursive call as your DFS tree is bounded by the maxTime. 
# Why Backtracking ?\nBecause we got at most 4 children of a node and no need of worrying out infinite recursive call as your DFS tree is bounded by the maxTime. Also look at constraints backtracking seems good bet.\n# Logic \n* Basically if you somehow were able reach to  the node 0  then you should update the sum you have with answer , this will be always valid as we have a conditional check " if(currTime+child.second<=maxTime)" while traversing. Thus we reach next recursive call only when our currTime is <=maxTime.\n\n* If the node\'s frequency is one then this means that it was visited the very first time and we can add its value to our sum variable.\n\n* Before recursive call pops off the stack undo our work by decrementing node from hashmap (Essence of Backtracking ).\n\n```\n    int ans=INT_MIN;// global variable\n\n    void dfs(vector<int>& values,vector<pair<int,int>> adj[],int& maxTime,int currTime,unordered_map<int,int>& frequency,int node,int sum)\n    {\n        frequency[node]++;// in both cases if visited before or first time increment its frequency\n        \n        if(frequency[node]==1)// visited first time\n            sum+=values[node];\n    \n        if(node==0)// arrived at destination aka node 0\n            ans=max(ans,sum);\n        \n         for(auto child:adj[node])// exploring children\n         {\n            if(currTime+child.second<=maxTime)// validation check\n                 dfs(values,adj,maxTime,currTime+child.second,frequency,child.first,sum);   \n         }\n    \n          if(--frequency[node]==0)frequency.erase(node);// backtrack from this node\n    }\n    \n    \n    int maximalPathQuality(vector<int>& values, vector<vector<int>>& edges, int maxTime) {\n        \n        int n=values.size();\n        \n        vector<pair<int,int>> adj[n];\n        \n        for(auto a:edges)\n        {\n            adj[a[0]].push_back({a[1],a[2]});\n            adj[a[1]].push_back({a[0],a[2]});// dont forget this undirected graph is given\n        }\n        \n        unordered_map<int,int> frequency;\n        \n        dfs(values,adj,maxTime,0,frequency,0,0);\n        \n        return ans;\n        \n    }\n```\n\n**The graph may not be connected**. This is just given to confuse us we only care about the component in which node 0 lies. No need to bother about the other components as we have to reach back to node 0.
['Backtracking', 'C++']