1443.cpp (1079B)
1 class Solution { 2 public: 3 int minTime(int n, vector<vector<int>> &edges, vector<bool> &hasApple) { 4 vector<vector<int>> adj(n, vector<int>()); 5 for (auto &e : edges) { 6 adj[e[0]].push_back(e[1]); 7 adj[e[1]].push_back(e[0]); 8 } 9 10 stack<pair<int, int>> st; 11 int res = 0; 12 13 st.push({0, -1}); 14 while (!st.empty()) { 15 if (st.top().first == -1) { 16 st.pop(); 17 18 auto [crnt, par] = st.top(); 19 st.pop(); 20 int count = 0; 21 22 for (int c : adj[crnt]) { 23 if (c == par) continue; 24 count += hasApple[c]; 25 } 26 27 res += count; 28 hasApple[crnt] = hasApple[crnt] || count; 29 continue; 30 } 31 32 auto [crnt, par] = st.top(); 33 st.push({-1, -1}); 34 35 for (int c : adj[crnt]) { 36 if (c == par) continue; 37 st.push({c, crnt}); 38 } 39 } 40 41 return res * 2; 42 } 43 };