# 1443. Minimum Time to Collect All Apples in a Tree
###### tags: `LeetCode`
## **Link**
https://leetcode.com/problems/minimum-time-to-collect-all-apples-in-a-tree/

## **Code**

class Solution {
public:
    void setParent(int n, vector<int> &parent, vector<int> &needDfs)
    {
        if(needDfs[parent[n]]==0)
        {
            needDfs[parent[n]]=1;
            setParent(parent[n],parent,needDfs);
        }
    }

    int dfs(int n, vector<vector<int>> &child, vector<int> &needDfs)
    {
        int rt=0,sz=child[n].size();
        for(int i=0;i<sz;i++)
        {
            if(needDfs[child[n][i]]==1)
            {
                rt=rt+2+dfs(child[n][i],child,needDfs);
            }
        }
        return rt;
    }

    int minTime(int n, vector<vector<int>>& edges, vector<bool>& hasApple)
    {
        vector<int> parent(n),needDfs(n,0); //父節點陣列、化簡樹陣列
        set<int> inTree; //存已經在樹裡面的點
        inTree.insert(0); 
        needDfs[0]=1;
        vector<vector<int>> child(n); //子節點陣列
        for(int i=0;i<n;i++)
            parent[i]=i;
        int sz=edges.size(),way;
        for(int i=0;i<sz;i++) //建單向樹
        {
            way=(inTree.find(edges[i][0])!=inTree.end())?1:0;
            inTree.insert(edges[i][way]);
            parent[edges[i][way]]=edges[i][(way+1)%2];
            child[edges[i][(way+1)%2]].push_back(edges[i][way]);
            if(hasApple[edges[i][way]])
            {
                needDfs[edges[i][way]]=1;
                setParent(edges[i][way],parent,needDfs);
            }
        }
        return dfs(0,child,needDfs); //dfs
    }
};

## date
**2023.01.11**

{%hackmd @nnks8908/background_leetcode %}