leetcode

0 class Solution {

1 public:

2 vector<int> countSubTrees(int n, vector<vector<int>> &edges, string labels) {

3 vector<vector<int>> adj(n, vector<int>()), count(n, vector<int>(26, 0));

4 vector<bool> visited(n, false);

5 vector<int> res(n);

6

7 for (auto &e : edges) {

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

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

10 }

11

12 stack<int> st;

13 st.push(0);

14 while (!st.empty()) {

15 int crnt = st.top();

16 if (visited[crnt]) {

17 st.pop();

18

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

20 if (visited[c]) continue;

21 for (int i = 0; i < 26; i++)

22 count[crnt][i] += count[c][i];

23 }

24 res[crnt] = ++count[crnt][labels[crnt] - 'a'];

25 visited[crnt] = false;

26 continue;

27 }

28

29 visited[crnt] = true;

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

31 if (visited[c]) continue;

32 st.push(c);

33 }

34 }

35

36 return res;

37 }

38 };