[3 solutions] simple count +  DFS +BFS + picture + comments + road metaphor
Solution 1: DFS  (Time/Space: O(N), O(N))  \nGiven the \u2018Y\u2019 shape nature of the tree branches, I was so confused in the contest and can not find a good
**Solution 1: DFS  (Time/Space: O(N), O(N))**  \nGiven the \u2018Y\u2019 shape nature of the tree branches, I was so confused in the contest and can not find a good way to avoid repeating counting.  \nBut remeber the great slogan, \'If you wanna be rich, build the rode first\'.\nWe only build the road from root to and only to ALL apples.\nSo, this is kind of like counting the total road length of the \'root to all apples\'. Once you get this total length, you need to double it since it is a back and forth journey for you.\n\n**Complexity Analysis:**\n\n**Time Complexity: O(N).  **\n\nThere is N nodes, N-1 edeges, each need be explore.\n\n\n**Space Complexity: O(N). **\n\nNoticed that adJList is used to store edges in both directions, so the total space is: 2*(N-1);\nPlus, the reucusion stakc also O(N) space in worst case. \nSo overall is: O(3N). After droping constant factor, you can get the space complexity: O(N).\nFor example,  we can check example 1, N=7, i.e., 7 nodes, 6 edges, adjacency list, adjList, need store 12 edges information. \n\n\n\nI will make a small illustration on Example one to make it better to understand.\n\n![image](https://assets.leetcode.com/users/codedayday/image_1589091777.png)\n\n\n```\nclass Solution {\npublic:\n    vector<vector<int>> adjList;\n    vector<bool> visited;\n    \n    // returned value: rode length from root to and only to ALL apples which can be found beyond and include node\n    int dfs(int node,vector<bool>& hasApple,int d){\n        visited[node]=true;\n        int result=d;\t//Initialize result as d.        \n        for(auto &child:adjList[node])\n            if(!visited[child]) {\n                int dist2apple=dfs(child,hasApple,d+1); //rode distance between root to ALL apples  beyound node \'child\'\n                if(dist2apple)  //If child has apples it\'ll return a non zero result which is the distance traveled upto that node.\n                    result+=dist2apple-d;                     \n            }\n        \n        return (hasApple[node]   // current \'node\' has apple\n                ||               // or  \n                result > d) ?    // offspring(s) of current \'node\' have apple(s)\n                result: 0;       // if true, we count the road length, otherwise, no road is needed.\n        \n    }\n    int minTime(int n, vector<vector<int>>& edges, vector<bool>& hasApple){\n        adjList.resize(n);\n        visited.resize(n,false);\n        for(auto& e:edges)\n            adjList[e[0]].push_back(e[1]),adjList[e[1]].push_back(e[0]);\n        return dfs(0,hasApple,0)*2;     //Result is the distance travelled doubled as per our observation.\n    }\n};\n// reference & credit @PhoneixDD: \n// https://leetcode.com/problems/minimum-time-to-collect-all-apples-in-a-tree/discuss/623679/C%2B%2B-Simple-DFS\n```\n\n**Solution 1b: DFS (without logging visiting info)**   (Time/Space: O(N), O(N))\nDue to the fact from_i < to_i, we know the node value of child is always bigger than parent. We do not neet extra variable to log visiting info.\n```\nclass Solution {  // Solution 1b: DFS\npublic://1044-1053-1058\n    int minTime(int n, vector<vector<int>>& edges, vector<bool>& hasApple) {\n        vector<vector<int> > G(n);\n        for(auto& e: edges) G[e[0]].push_back(e[1]),G[e[1]].push_back(e[0]);        \n        return dfs(G, hasApple, 0, 0) * 2;\n    }\n    \nprivate:\n    \n    //returned value: the road length from root to all apples within the subtree rooted at cur\n    int dfs(vector<vector<int> >& G, vector<bool>& hasApple, int cur, int d){\n        int ans = d;    \n        for(auto& next: G[cur]){    \n            if(next < cur) continue;//if ture, this is parent of cur, skip \n            int dist2app = dfs(G, hasApple, next, d+1);\n            if(dist2app != 0)\n                ans += dist2app - d;\n        }\n        return hasApple[cur] || ans > d ? ans : 0;        \n    }\n};\n```\n**Solution 2:  simple count ( Time/Space: O(NlogN); O(1) )**\nIf you carefully check the figure in the right-hand-side, the road length is is also same as the number of visited vodes for you to reach all apples.\nSo we got second solution.\n\nFind the apples from the end and check where you come from, then, let the start point of edge true(as an apple). Finally, count the number of edge you need to go through and it cost 2 seconds for each edge(back and forth).\n```\nclass Solution { // Solution 2: simple count\npublic: // Time/Space: O(NlogN); O(1)\n    int minTime(int n, vector<vector<int>>& edges, vector<bool>& hasApple) {\n        int cnt = 0;           \n        sort(edges.begin(), edges.end()); // this is must to ensure value of parent is smaller than child\n        //for(int i=n-2; i>=0; i--)   // also ok\n        for(int i= edges.size() - 1; i>=0; i--)  //Note1: visit most distant child first       \n            if(hasApple[edges[i][1]]){\n                cnt++;\n                hasApple[edges[i][0]] = true;\n            }         \n        return cnt*2;\n    }\n};\n```\n\n**Solution 2b: simple count ( Time/Space: O(N); O(N) )**\nThanks for the push from @jdanray, who complains about the O(NlogN) time cost, so I increase the O(1) space to O(N) to reduce the time cost from O(NlogN) to O(N)\n\n```\nclass Solution { // Solution 2b: simple count\npublic: // Time/Space: O(N); O(N)\n    int minTime(int n, vector<vector<int>>& edges, vector<bool>& hasApple) {        \n        //unordered_map<int,int> parents; // ok, if you hate thinking about default value for vector based hashmap solution.\n        vector<int> parents(n,0); // Be careful about the default value.  parents[i]:= the parent of node i.\n        for(auto& e: edges) parents[e[1]] = e[0];        \n        for(int i= n - 1; i>=0; i--)  //Note1: visit most distant child first       \n            if(hasApple[i]) hasApple[parents[i]] = true; // if a child is apple, convert their parent into apple            \n        int cnt = count(hasApple.begin(), hasApple.end(), true); // count how many apples in total, \n        // if count is non zero, then \'cnt\' is the apple/node count of purely apple sub-tree, then edge count is: cnt-1\n        return cnt == 0 ? 0 : (cnt-1)*2;         \n    }\n};\n```\nRef:\nhttps://leetcode.com/problems/minimum-time-to-collect-all-apples-in-a-tree/discuss/623969/C%2B%2B-Simple-Solution-O(n)\n\n**Solution 3: BFS  (Time/Space: O(N), O(N))**\n```\nclass Solution {\npublic:\n    int minTime(int n, vector<vector<int>>& edges, vector<bool>& has) {\n        //1: build the Graph: G\n        vector<int> G[n],dist(n,1e9),par(n,1e9);\n        for(auto& x:edges){\n            G[x[0]].push_back(x[1]);\n            G[x[1]].push_back(x[0]);\n            par[x[1]]=x[0];\n        }\n        \n        //2: measure the distances of each node from root\n        queue<int> q{{0}};\n        dist[0]=0;        \n        while(!q.empty()){\n            int cur = q.front(); q.pop();\n            for(int x:G[cur]){\n                if(dist[x]==1e9){\n                    dist[x]=dist[cur]+1;\n                    q.push(x);\n                }\n            }\n        }\n        \n        //3: accumulate the distance from child to its first visited parent\n        int cnt=0;\n        vector<int> vis(n,0);\n        for(int i=n-1;i>=0;i--){\n            if(has[i]==true && vis[i]==0){ // i: node with apple and unvisited yet\n                int q = i; // find the first visited parent of i\n                while(par[q]!=1e9 and vis[q]==0){\n                    vis[q]=1;\n                    q = par[q];\n                }// now, q points to the first visited parent of i\n                vis[i]=1;                \n                cnt += 2*(dist[i]-dist[q]);\n            }\n        }\n        return cnt;\n    }\n};\n```\nReference and credit @wanottle:\nhttps://leetcode.com/problems/minimum-time-to-collect-all-apples-in-a-tree/discuss/624126/C%2B%2B-or-BFS-or-Simple-Solution-with-explanation\n
['Depth-First Search', 'Breadth-First Search', 'C']