C++-এ ট্রিতে সব আপেল কালেক্ট করতে ন্যূনতম সময়

একটি আনডিরেক্টেড ট্রি আছে n ভের্টেক্স দিয়ে (০ থেকে n-1)। কিছু ভের্টেক্সে আপেল আছে। এক এজ পার করতে ১ সেকেন্ড লাগে। সিটি ০ থেকে শুরু করে সব আপেল কালেক্ট করে আবার সিটি ০ এ ফেরার ন্যূনতম সময় বের করতে হবে।

ইনপুট: n=7, edges=[[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple=[false,false,true,false,true,true,false] → আউটপুট: 8

সমাধানের ধাপগুলো (DFS):

অ্যাডজেসেন্সি লিস্ট graph বানাব
dfs(node, parent): সাবট্রি থেকে আপেল কালেক্ট করার কস্ট রিটার্ন করব
যদি সাবট্রিতে আপেল থাকে, তবে সেই এজ دوبায়_traverse করতে হবে (২ সেকেন্ড)
গ্লোবাল ret এ টোটাল টাইম যোগ করব

উদাহরণ

নিচের কোডটি দেখুন −

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6;

class Solution {
public:
    set<int> visited;
    int ret;
    int dfs(int node, int par, vector<bool>& a, vector<int> graph[]) {
        int temp = 0;
        for (int x : graph[node]) {
            if (x == par)
                continue;
            temp += dfs(x, node, a, graph);
        }
        ret += temp * 2;
        return a[node] + temp > 0;
    }
    int minTime(int n, vector<vector<int>>& e, vector<bool>& a) {
        ret = 0;
        vector<int> graph[n];
        for (int i = 0; i < e.size(); i++) {
            graph[e[i][0]].push_back(e[i][1]);
            graph[e[i][1]].push_back(e[i][0]);
        }
        dfs(0, -1, a, graph);
        return ret;
    }
};

int main() {
    Solution ob;
    vector<vector<int>> v = {{0,1},{0,2},{1,4},{1,5},{2,3},{2,6}};
    vector<bool> v1 = {false,false,true,false,true,true,false};
    cout << (ob.minTime(7, v, v1));
}

ইনপুট

7, {{0,1},{0,2},{1,4},{1,5},{2,3},{2,6}}, {false,false,true,false,true,true,false}