C++ | BFS | Simple Solution with explanation
Calculate distances of all nodes w.r.t. to root i.e. 0. (Using simple BFS). Also store parent for each node.\n2. Notice distance between any two nodes x, y is a
1. Calculate distances of all nodes w.r.t. to root i.e. 0. (Using simple BFS). Also store parent for each node.\n2. Notice distance between any two nodes x, y is abs(dist[x]-dist[y]).\n3. Now start traversing the list of nodes where apple is. Preferably backwards.\n4. When you see a node with apple you travel towards root including each edge twice untill you find some already visited node or reach root obviously after which you can\'t go any further.\n5. Why till a visited node? Because if it is already visited it implies that path from that node to root is already included and since we want shortest time we need not visit it again.\n\n```\nclass Solution {\npublic:\n    int minTime(int n, vector<vector<int>>& edges, vector<bool>& has) {\n        vector<int> v[n],dist(n,1e9),vis(n,0),par(n,1e9);\n        for(auto x:edges){\n            v[x[0]].push_back(x[1]);\n            v[x[1]].push_back(x[0]);\n            par[x[1]]=x[0];\n        }\n        queue<int> q;\n        q.push(0);dist[0]=0;\n        \n        while(!q.empty()){\n            int cur = q.front();\n            q.pop();\n            for(int x:v[cur]){\n                if(dist[x]==1e9){\n                    dist[x]=dist[cur]+1;\n                    q.push(x);\n                }\n            }\n        }\n        int cnt=0;\n        for(int i=n-1;i>=0;i--){\n            if(has[i]==true and vis[i]==0){\n                int q = i;\n                while(par[q]!=1e9 and vis[q]==0){\n                    vis[q]=1;\n                    q = par[q];\n                }\n                vis[i]=1;\n                cnt+=(2*(abs(dist[i]-dist[q])));\n            }\n        }\n        return cnt;\n    }\n};
[]