Simple DFS solution (C++)
We will do DFS in this problem. We have the condition here that we can visit a node any number of times but we shall add its value only once for that path for t
We will do DFS in this problem. We have the condition here that we can visit a node any number of times but we shall add its value only once for that path for the calculation of its quality. \n\nSo, we would require a visited array which would keep track of the visited nodes so that we do not add its value again into the quality score. \n\nHere, we are doing DFS and we increase the count of that node in visited array indicating how many times we have visited that node. If its being visited for the first time, we add its value to our sum. After we have processed all its neighbours, we then mark the current node as unvisited i.e. we reduce the count of that node from the visited array. \n\nWe do not use a boolean visited array since if we go that way we would not be able to track visited properly since if we turn visited back to false after processing its neighbours, it would mean we treat that node as non visited even if its been visited multiple times before. To account for that, we use counter based visited array which increases or decreases the visited count thus serving its purpose.\n\nThe code provided below is self explanatory and I am sure you would be able to understand it easily.\n\n```\nclass Solution {\npublic:\n    int maximalPathQuality(vector<int>& values, vector<vector<int>>& edges, int maxTime) {\n        int n = values.size();\n        int res = values[0];\n        vector<vector<pair<int,int>>> graph(n);\n        for(int i=0;i<edges.size();i++)\n        {\n            graph[edges[i][0]].push_back({edges[i][1], edges[i][2]});\n            graph[edges[i][1]].push_back({edges[i][0], edges[i][2]});\n        }\n        \n        vector<int> visited(n, 0);\n        dfs(graph, values, visited, res, 0, 0, 0, maxTime);\n        return res;\n    }\n    \n    void dfs(vector<vector<pair<int,int>>>& graph, vector<int>& values, vector<int>& visited, int& res, int node, int score, int time, int& maxTime)\n    {\n        if(time > maxTime)\n            return;\n        \n        if(visited[node] == 0)\n            score += values[node];\n        \n \xA0 \xA0 \xA0 \xA0visited[node]++;\n\t\t\n \xA0 \xA0 \xA0\n \xA0 \xA0 \xA0 \xA0if(node == 0)\n            res = max(res, score);\n        \n        for(auto it : graph[node])\n        {\n            int neigh = it.first;\n            int newTime = time + it.second;\n            dfs(graph, values, visited, res, neigh, score, newTime, maxTime);\n        }\n        \n        visited[node]--;\n    }\n};\n```\n
['Depth-First Search', 'C', 'C++']