You are given a tree (i.e. a connected, undirected graph that has no cycles) consisting of n nodes numbered from 0 to n - 1 and exactly n - 1 edges. The root of the tree is the node 0, and each node of the tree has a label which is a lower-case character given in the string labels (i.e. The node with the number i has the label labels[i]).

The edges array is given on the form edges[i] = [ai, bi], which means there is an edge between nodes ai and bi in the tree.

Return an array of size n where ans[i] is the number of nodes in the subtree of the ith node which have the same label as node i.

A subtree of a tree T is the tree consisting of a node in T and all of its descendant nodes.

&nbsp;
Example 1:

Input: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], labels = "abaedcd"
Output: [2,1,1,1,1,1,1]
Explanation: Node 0 has label 'a' and its sub-tree has node 2 with label 'a' as well, thus the answer is 2. Notice that any node is part of its sub-tree.
Node 1 has a label 'b'. The sub-tree of node 1 contains nodes 1,4 and 5, as nodes 4 and 5 have different labels than node 1, the answer is just 1 (the node itself).


Example 2:

Input: n = 4, edges = [[0,1],[1,2],[0,3]], labels = "bbbb"
Output: [4,2,1,1]
Explanation: The sub-tree of node 2 contains only node 2, so the answer is 1.
The sub-tree of node 3 contains only node 3, so the answer is 1.
The sub-tree of node 1 contains nodes 1 and 2, both have label 'b', thus the answer is 2.
The sub-tree of node 0 contains nodes 0, 1, 2 and 3, all with label 'b', thus the answer is 4.


Example 3:

Input: n = 5, edges = [[0,1],[0,2],[1,3],[0,4]], labels = "aabab"
Output: [3,2,1,1,1]


&nbsp;
Constraints:


	1 &lt;= n &lt;= 105
	edges.length == n - 1
	edges[i].length == 2
	0 &lt;= ai, bi &lt; n
	ai != bi
	labels.length == n
	labels is consisting of only of lowercase English letters.


class Solution:
    """
    we can solve this using dfs based approach
    identify the root of the tree and start a dfs from there 
    """
    def countSubTrees(self, n: int, edges: List[List[int]], labels: str) -> List[int]:
        graph_map = {i: set() for i in range(n)}
        for edge in edges:
            graph_map[edge[0]].add(edge[1])
            graph_map[edge[1]].add(edge[0])
            
        result = [None for _ in range(n)]
        
        visited = set()
        def dfs(index):
            visited.add(index)
            temp = [0 for _ in range(26)]
            temp[ord(labels[index])-97]+=1
            for idx in graph_map[index]:
                if idx not in visited:
                    x = dfs(idx)
                    temp = [a + b for a, b in zip(temp, x)]
            result[index] = temp[ord(labels[index])-97]
            return temp
        
        dfs(0)
        return result
class Solution {
  int[] res;

  public int[] countSubTrees(int n, int[][] edges, String labels) {
    res = new int[n];
    Map<Integer, List<Integer>> adjList = new HashMap<>();
    for (int i = 0; i < n; i++) {
      adjList.put(i, new ArrayList<>());
    }
    for (int[] edge : edges) {
      adjList.get(edge[0]).add(edge[1]);
      adjList.get(edge[1]).add(edge[0]);
    }
    postOrderDfs(adjList, labels, 0, -1);
    return res;
  }

  int[] postOrderDfs(Map<Integer, List<Integer>> adjList, String labels, int n, int parent) {
    int[] chars = new int[26];
    chars[labels.charAt(n) - 'a']++;
    for (int next : adjList.get(n)) {
      if (next != parent) mergeArrCounts(chars, postOrderDfs(adjList, labels, next, n));
    }
    res[n] = chars[labels.charAt(n) - 'a'];
    return chars;
  }

  // Merge from B to A
  void mergeArrCounts(int[] A, int[] B) {
    for (int i = 0; i < 26; i++) {
      A[i] += B[i];
    }
  }
}
class Solution {
    vector<int> ans;
    vector<vector<int>> graph;
    string global;
public:
    
    
    vector<int> getAns(int u, int parent){
        ans[u] = 1;
        char rootChar = global[u];
        vector<int> toReturn = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
        
        for(int adj : graph[u]){
            if(adj != parent){
                vector<int> c = getAns(adj, u);
                for(int i = 0 ; i < 26 ; i++){
                    toReturn[i] += c[i];
                } 
                ans[u] += c[rootChar-'a'];
            }
            
        }
        toReturn[rootChar-'a'] += 1;
        return toReturn;
    }
    
    vector<int> countSubTrees(int n, vector<vector<int>>& edges, string labels) {
        ans.resize(n);
        graph.resize(n);
        global = labels;
        
        
        
        for(vector<int> edge : edges){
            graph[edge[0]].push_back(edge[1]);
            graph[edge[1]].push_back(edge[0]);
        }
        
        int root = 0;
        int parent =  -1;  
        getAns(root, parent);
        return ans;
 
    }
};
var countSubTrees = function(n, edges, labels) {
    const adj = [];

    for (let i = 0; i < n; i++) {
        adj[i] = [];
    }

    for (const [u, v] of edges) {
        adj[u].push(v);
        adj[v].push(u);
    }

    const resCount = new Array(n).fill(0);

    dfs(0, -1);

    return resCount;

    function dfs(node, parent) {
        const label = labels.charCodeAt(node) - 97;

        const charCount = new Array(26).fill(0);

        charCount[label] = 1;

        for (const childNode of adj[node]) {
            if (childNode == parent) continue;

            const subCount = dfs(childNode, node);

            for (let i = 0; i < 26; i++) {
                charCount[i] += subCount[i];
            }
        }

        resCount[node] = charCount[label];
        return charCount;
    }
}
Number of Nodes in the Sub-Tree With the Same Label