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

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.

class Solution {
    void add(int node, vector<list<int>>& edge, unordered_map<char,int>& m, string& s, vector<int>& res) {
        if(!res[node]) {
            res[node] = 1;
            for(auto endPoint : edge[node]) {
                unordered_map<char,int> nm;
                add(endPoint, edge, nm, s, res);
                for(auto& entity : nm) {
                    m[entity.first] += entity.second;
                }
            }
            res[node] = ++m[s[node]];
        }
    }
public:
    vector<int> countSubTrees(int n, vector<vector<int>>& edges, string labels) {
        vector<list<int>> sortedEdge(n, list<int>()), parent(n, list<int>());
        vector<int> res(n);
        unordered_map<char, int> m;
        for(auto& edge : edges) {
            sortedEdge[edge.front()].push_back(edge.back());
            sortedEdge[edge.back()].push_back(edge.front());
        }
        add(0, sortedEdge, m, labels, res);
        return res;
    }
};