Beats 100% time & memory, O(n) in C++/Rust/Go
Intuition\nAs we have n nodes, n - 1 edges, and from each node exists path to node 0 - it means each node has only one parent, so we could store only index of p
# Intuition\nAs we have $$n$$ nodes, $$n - 1$$ edges, and from each node exists path to node `0` - it means each node has only one parent, so we could store only index of parent to save space.\n\n# Approach\nFrom each node having apple traverse path to node `0`, marking used edges (to visit each node only once) and counting them.\n\n# Complexity\n- Time complexity:\n$$O(n)$$ or actually $$O(3*n)$$ as we copy all edges ($$n - 1$$), then traverse `hasApple` array ($$n$$), and finally scan `parentEdge` till already visited node is reached ($$n$$)\n\n- Space complexity:\n$$O(n)$$ as we store edges\n\n# Code in C++\n```\nclass Solution {\npublic:\n    int minTime(const int n, const std::vector<std::vector<int>> & edges, const std::vector<bool> & hasApple) {\n        std::vector<int> parentEdge(n, -1);\n        for (const auto & edge : edges) {\n            if (parentEdge[edge[1]] == -1) {\n                parentEdge[edge[1]] = edge[0];\n            } else {\n                parentEdge[edge[0]] = edge[1];\n            }\n        }\n\n        int result = 0;\n        for (int i = 0; i < n; ++i) {\n            if (!hasApple[i]) {\n                continue;\n            }\n\n            for (int node = i; parentEdge[node] != -1; ++result) {\n                const auto parentNode = parentEdge[node];\n                parentEdge[node] = -1;\n                node = parentNode;\n            }\n        }\n        return result * 2;\n    }\n};\n```\n\n# Code in Rust\n```\nimpl Solution {\n    pub fn min_time(n: i32, edges: Vec<Vec<i32>>, has_apple: Vec<bool>) -> i32 {\n        let mut parent_edge = vec![-1; n as usize];\n        for edge in edges.into_iter() {\n            if parent_edge[edge[1usize] as usize] == -1 {\n                parent_edge[edge[1usize] as usize] = edge[0usize];\n            } else {\n                parent_edge[edge[0usize] as usize] = edge[1usize];\n            }\n        }\n\n        let mut result = 0;\n        for i in 0..(n as usize) {\n            if !has_apple[i] {\n                continue;\n            }\n\n            let mut node = i as i32;\n            while parent_edge[node as usize] != -1 {\n                let parent_node = parent_edge[node as usize];\n                parent_edge[node as usize] = -1;\n                node = parent_node;\n                result += 1;\n            }\n        }\n        result * 2\n    }\n}\n```\n\n# Code in Go\n```\nfunc minTime(n int, edges [][]int, hasApple []bool) int {\n    parentEdge := make([]int, n)\n    for i := 0; i < n; i++ {\n        parentEdge[i] = -1\n    }\n    for i := 0; i < n - 1; i++ {\n        if parentEdge[edges[i][1]] == -1 {\n            parentEdge[edges[i][1]] = edges[i][0]\n        } else {\n            parentEdge[edges[i][0]] = edges[i][1]\n        }\n    }\n\n    result := 0\n    for i := 0; i < n; i++ {\n        if !hasApple[i] {\n            continue\n        }\n\n        for node := i; parentEdge[node] != -1; result++ {\n            parentNode := parentEdge[node]\n            parentEdge[node] = -1\n            node = parentNode\n        }\n    }\n    return result * 2\n}\n```
['Array', 'C++', 'Go', 'Rust']