# 1519. Number of Nodes in the Sub-Tree With the Same Label

• Time: $O(n)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 class Solution { public: vector countSubTrees(int n, vector>& edges, string labels) { vector ans(n); vector> tree(n); for (const vector& edge : edges) { const int u = edge[0]; const int v = edge[1]; tree[u].push_back(v); tree[v].push_back(u); } dfs(tree, 0, -1, labels, ans); return ans; } private: vector dfs(const vector>& tree, int u, int parent, const string& labels, vector& ans) { // count[i] := # of letters down from 'a' + i vector count(26); for (const int v : tree[u]) { if (v == parent) continue; vector childCount = dfs(tree, v, u, labels, ans); for (int i = 0; i < 26; ++i) count[i] += childCount[i]; } ans[u] = ++count[labels[u] - 'a']; // The u itself return count; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 class Solution { public int[] countSubTrees(int n, int[][] edges, String labels) { int[] ans = new int[n]; List[] graph = new List[n]; for (int i = 0; i < n; ++i) graph[i] = new ArrayList<>(); for (int[] edge : edges) { final int u = edge[0]; final int v = edge[1]; graph[u].add(v); graph[v].add(u); } dfs(graph, 0, -1, labels, ans); return ans; } private int[] dfs(List[] graph, int u, int parent, final String labels, int[] ans) { // count[i] := # of letters down from 'a' + i int[] count = new int[26]; for (final int v : graph[u]) { if (v == parent) continue; int[] childCount = dfs(graph, v, u, labels, ans); for (int i = 0; i < 26; ++i) count[i] += childCount[i]; } ans[u] = ++count[labels.charAt(u) - 'a']; // The u itself return count; } }