[C++] DP on tree
Given an undirected tree, the time to walk over an edge is 1s. There are apples on the tree nodes. What is the least time to collect all apples on the tree star
Given an undirected tree, the time to walk over an edge is 1s. There are apples on the tree nodes. What is the least time to collect all apples on the tree starting from node 0?\n\n# Explanation\n\nThis is a simple DP problem. Let `child[i]` denote the list of children of node `i`, `subHasApple[i]` denote whether there is apple in the subtree of node `i`. Then the time needed to pick all the apples in the subtree of node `i` is: \n\n```\ntime[i] = sum(2 + time[j]) for j in child[i] and subHasApple[j] is True\n```\n\nThe extra `2` is the time to walk to and back from the subtree.\n\n# Solution\n\n```cpp\nclass Solution {\n    vector<vector<int>> G;\n    vector<int> fa;\n    vector<bool> hasApple;\n    \n    // returns time\n    int dfs(int u, bool& hasApple1) {\n        int totTime = 0;\n        hasApple1 = false;\n        for (int v: G[u]) {\n            if (v == fa[u]) continue;\n            fa[v] = u;\n            bool hasApple2 = false;\n            int time = dfs(v, hasApple2);\n            if (hasApple2) {\n                hasApple1 = true;\n                totTime += time + 2;\n            }\n        }\n        if (hasApple[u]) hasApple1 = true;\n        return totTime;\n    }\n    \npublic:\n    int minTime(int n, vector<vector<int>>& edges, vector<bool>& hasApple) {\n        G = vector<vector<int>>(n, vector<int>());\n        fa = vector<int>(n, -1);\n        this->hasApple = hasApple;\n        \n        for (int i = 0; i < edges.size(); i++) {\n            G[edges[i][0]].push_back(edges[i][1]);\n            G[edges[i][1]].push_back(edges[i][0]);\n        }\n        \n        fa[0] = -1;\n        bool subtreeHasApple = false;\n        return dfs(0, subtreeHasApple);\n    }\n};\n```\n
[]