# 1519. Number of Nodes in the Sub-Tree With the Same Label
###### tags: `LeetCode`
## **Link**
https://leetcode.com/problems/number-of-nodes-in-the-sub-tree-with-the-same-label/

## **Code: 極限時間超大遞迴 ver. (2566 ms)**

class Solution {
public:
    map<char,int> doit(int n, vector<int> &ans, vector<vector<int>> &child, string &labels)
    {
        map<char,int> mp,kp;
        ++mp[labels[n]];
        for(int i=0;i<child[n].size();++i)
        {
            kp.clear();
            kp = doit(child[n][i],ans,child,labels);
            for(pair<char,int> v:kp)
            {
                mp[v.first]+=v.second;
            }
        }
        ans[n]=mp[labels[n]];
        return mp;
    }
    
    vector<int> countSubTrees(int n, vector<vector<int>>& edges, string labels) 
    {
        vector<vector<int>> child(n); //子節點陣列
        set<int> inTree; //存有在樹裡面的點
        inTree.insert(0);
        int chi;
        sort(edges.begin(),edges.end());
        for(int i=0;i<n-1;++i)
        {
            chi=(inTree.find(edges[i][0]) != inTree.end())?1:0; //找誰是子節點
            inTree.insert(edges[i][chi]);
            child[edges[i][chi^1]].push_back(edges[i][chi]);
        }
        vector<int> ans(n);
        doit(0,ans,child,labels);
        return ans;
    }
};

## **Code: 快一點的迴圈 ver. (1292 ms)**

class Solution {
public:
    vector<int> countSubTrees(int n, vector<vector<int>>& edges, string labels) 
    {
        vector<int> parent(n,-1);
        unordered_map<char,int> words;
        unordered_set<int> inTree;
        vector<bool> visited(n,false),hasChild(n,false);
        inTree.insert(0);
        int chi,now;
        vector<int> ans(n,0);
        for(int i=0;i<n-1;++i)
        {
            chi=(inTree.find(edges[i][0]) != inTree.end())?1:0;
            parent[edges[i][chi]]=edges[i][chi^1];
            hasChild[edges[i][chi^1]]=true;
            inTree.insert(edges[i][chi]);
        }
        for(int i=0;i<n;++i)
        {
            if(!hasChild[i])
            {
                words.clear();
                now=i;
                while(now!=-1)
                {
                    if(!visited[now])
                    {
                        words[labels[now]]++;
                        visited[now]=true;
                    }
                    ans[now]+=words[labels[now]];
                    now=parent[now];
                }
            }
        }
        return ans;
    }
};

## date
**2023.01.12**

{%hackmd @nnks8908/background_leetcode %}