leetcode

0 class Solution {

1 public:

2 int minTime(int n, vector<vector<int>> &edges, vector<bool> &hasApple) {

3 vector<vector<int>> adj(n, vector<int>());

4 for (auto &e : edges) {

5 adj[e[0]].push_back(e[1]);

6 adj[e[1]].push_back(e[0]);

7 }

8

9 stack<pair<int, int>> st;

10 int res = 0;

11

12 st.push({0, -1});

13 while (!st.empty()) {

14 if (st.top().first == -1) {

15 st.pop();

16

17 auto [crnt, par] = st.top();

18 st.pop();

19 int count = 0;

20

21 for (int c : adj[crnt]) {

22 if (c == par) continue;

23 count += hasApple[c];

24 }

25

26 res += count;

27 hasApple[crnt] = hasApple[crnt] || count;

28 continue;

29 }

30

31 auto [crnt, par] = st.top();

32 st.push({-1, -1});

33

34 for (int c : adj[crnt]) {

35 if (c == par) continue;

36 st.push({c, crnt});

37 }

38 }

39

40 return res * 2;

41 }

42 };