Slightly trick question , requires logical thinking || C++ Code with hints provided
Just think about how can you really reach every apple in shortest time . The answer is For every pair of apples , reach them through their lowest common ancesto
Just think about how can you really reach every apple in shortest time . The answer is For every pair of apples , reach them through their lowest common ancestor . \n\nThats why we call first left and right subtree of root and ask them if they got an apple in their subtree and then we just add up the answer if one of them or both of them says "YES" .or if node itself got an apple .\n\n```\nclass Solution {\n    \n    \n    int dfs(vector<int> adj[] , vector<bool>& vis , vector<bool>& hasApple , int root)\n    {\n        vis[root] = 1 ;\n        \n        int ans = 0;\n        \n        for(auto children : adj[root])\n        {\n            if(!vis[children])\n            {\n                ans+= dfs(adj , vis , hasApple , children ) ;\n            }\n        }\n        \n        if(root == 0) return ans ;\n        \n        if(ans > 0 || hasApple[root])\n        {\n            return ans+2 ;\n        }\n        \n        return 0;\n    }\n    \npublic:\n    int minTime(int n, vector<vector<int>>& edges, vector<bool>& hasApple) {\n\n        vector<int> adj[n] ;\n        \n        for(auto &x : edges)\n        {\n            adj[x[0]].push_back(x[1]);\n            adj[x[1]].push_back(x[0]);\n\n        }  \n        \n        vector<bool > vist(n , 0);\n        \n       return dfs(adj , vist , hasApple , 0 ) ;\n        \n        \n    }\n    \n    \n    \n};
[]