5465. 子树中标签相同的节点数（图论）

class Solution {
public:
    int vis[100001]{0};
    vector<int>ans;
    vector<int>  dfs(vector<vector<int>> & g,int u,string & labels){
        vector<int> count(26);
            if(vis[u]) return count;
        vis[u]=1;
        for(auto v:g[u]){
            if(!vis[v]){
                vector<int>temp=dfs(g,v,labels);
                for(int i=0;i<26;i++)
                    count[i]+=temp[i];
            } 
        }
        ans[u]=++count[labels[u]-'a'];
        return count;
        
}
    vector<int> countSubTrees(int n, vector<vector<int>>& edges, string labels) {
        vector<vector<int>> g;
        g.resize(n);
         for(auto v: edges){
            g[v[0]].push_back(v[1]);
             g[v[1]].push_back(v[0]);
        }
        ans.resize(n);
        dfs(g,0,labels);    
        return ans;
    }
};


// class Solution {
//     vector<vector<int>> tree;
//     vector<bool> vis;
//     vector<int> ans;
// public:
//     vector<int> countSubTrees(int n, vector<vector<int>>& edges, string labels) {
//         tree.resize(labels.size());
//         vis.resize(labels.size(), false);
//         ans.resize(labels.size());
//         for (auto& e : edges) {
//             tree[e[0]].emplace_back(e[1]);
//             tree[e[1]].emplace_back(e[0]);
//         }
//         vector<int> tmp(26);
//         dfs(0, tmp, labels);
//         return ans;
//     }

//     void dfs(int in, vector<int>& a, string& labels) {
//         if (vis[in]) return; vis[in] = true;

// 	vector<int> tmp(26);
// 	for (auto& out : tree[in]) dfs(out, tmp, labels);
//         ans[in] = ++tmp[labels[in] - 'a'];
//         for (int i = 0; i < 26; ++i) a[i] += tmp[i];
//     }
// };
// class Solution {
//     unordered_map<int,unordered_set<int>> m;
//     vector<int> ans;
// public:
//     vector<int> countSubTrees(int n, vector<vector<int>>& edges, string labels) {
//         for(auto& e : edges)
//         {
//             m[e[0]].insert(e[1]);
//             m[e[1]].insert(e[0]);
//         }
//         ans.resize(n);
//         vector<bool> vis(n,false);
//         dfs(0,labels,vis);
//         return ans;
//     }
//     vector<int> dfs(int root, string& labels,vector<bool> &vis)
//     {
//         vector<int> count(26,0), temp;
//         vis[root] = true;//访问过了
//         for(auto it = m[root].begin(); it != m[root].end(); ++it)
//         {
//             if(vis[*it])
//                 continue;
//             temp = dfs(*it,labels,vis);
//             for(int i = 0; i < 26; ++i)
//                 count[i] += temp[i];//把子树的字符计数更新到本节点
//         }
//         ans[root] = ++count[labels[root]-'a'];//加上自己的
//         return count;//返回字数的计数
//     }
// };